Facebook Pixel

752. Open the Lock

MediumBreadth-First SearchArrayHash TableString
Leetcode Link

Problem Description

In this problem, we have a lock that is represented by 4 circular wheels, each with digits from 0 to 9. The lock opens when the wheels show a specific combination of numbers called the target. We can turn one wheel at a time which will either increase or decrease the digit on the wheel by 1. The twist here is that there are certain combinations which are "deadends", meaning if we reach any of these combinations, the lock gets stuck and we can no longer manipulate it. Our goal is to find the minimum number of moves required to reach the target combination from the starting position '0000', while avoiding these deadends. If it's not possible to reach the target, we should return -1.

The challenge involves figuring out the shortest path to the target without hitting any deadends. It's like navigating a maze where each wheel turn changes your path slightly and you're trying to find the quickest route to the exit (target combination).

Flowchart Walkthrough

First, let's analyze the problem using the Flowchart. Here’s a detailed step-by-step examination:

Is it a graph?

  • Yes: Each state of the lock (i.e., "0000" to "9999") can be considered a node, and transitions between these states form edges.

Is it a tree?

  • No: The graph is not inherently hierarchical and can have cycles (e.g., going from "0000" to "0001" and back).

Is the problem related to directed acyclic graphs (DAGs)?

  • No: Although the states transition, this problem doesn’t involve topological properties of DAGs.

Is the problem related to shortest paths?

  • Yes: The goal is to find the shortest path from the initial state "0000" to the target lock combination.

Is the graph weighted?

  • No: Each step or move from one state to another (like from "0000" to "0001") can be considered as having the same weight or cost, typically one move.

Conclusion: The flowchart indicates that the Breadth-First Search (BFS) algorithm is suited for this type of unweighted shortest path problem in a graph structure, as it efficiently explores nodes layer by layer until reaching the target combination.

Intuition

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. BFS is an ideal choice for finding the shortest path on an unweighted graph or in our case, the fewest number of moves to reach the target. Each state of the lock can be treated as a node in the graph and each possible turn of a wheel can be considered as an edge to a new node.

Here's our plan of attack:

  1. BFS: We will perform a bidirectional BFS, starting from both the initial '0000' state and the target state. Bidirectional BFS can be more efficient than standard BFS as it may reduce the search space, because the searches from both ends will meet in the middle.

  2. Next States Generation: For each state (lock combination), we need to consider all possible "next" states. We can achieve this by writing a function to turn each wheel forward or backward, generating up to 8 new combinations from each state.

  3. Deadends Avoidance: Before we even start searching, we should put all deadends in a set for quick access and to make sure we never enqueue these states in our BFS.

  4. Searching for Connection: During the BFS, we explore nodes level by level, alternating expansion between the start and target searching blocks. If we encounter a node/state that's already been reached from the other direction, we have found a connection, and we can calculate the total steps taken.

  5. Handling Corner Cases: We check if the target is the initial lock state '0000', in which case we return 0 as no moves are required. Similarly, if '0000' is in the deadends, we return -1 because it's impossible to start.

Through these steps, the provided solution effectively finds the shortest path — that is, the minimum number of moves — to unlock the lock or determines that it's not possible.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution follows the BFS strategy described in the intuition:

  1. Deadend Preprocessing: Store all the deadends into a set called s for O(1) access time. This is important to quickly check whether a generated combination is a deadend or not, allowing us to skip it if necessary.

  2. Handling Base Cases: If the target is the same as the initial state (i.e., '0000'), we return 0 because no moves are needed. If '0000' is in the deadends set, we return -1 as we cannot start.

  3. Bidirectional BFS Initialization: Two hash maps m1 and m2 are initialized to represent the BFS layers starting from '0000' and target, respectively. Each map holds states as keys and the number of moves to reach them as values. Two double-ended queues q1 and q2 are also initiated to hold the states for processing.

  4. BFS with Two Queues: The core of the BFS occurs with two queues, where the method extend attempts to add adjacent states to the smaller queue, to ensure we always expand the search frontier with fewer nodes. This is a performance optimization that leverages the bidirectional search.

  5. Generating Adjacent States: The next method is important for the state space exploration. For each of the four wheels in a given state, it generates 2 adjacent states: one by increasing the digit and one by decreasing it while handling the wrap-around from '9' to '0' and '0' to '9'.

  6. Searching and Building Layers: Each expansion with the extend method takes a state p from the queue, checks all adjacent states generated by next(p) if any is not a deadend or already visited. If it finds the state in the opposite map (indicating that the two BFS meet), it returns the total move count. Otherwise, it updates the map with the new move count and enqueues the state.

  7. Reaching the Target: The algorithm continues this process until the queues are empty or until the searches from both ends meet - at which point it returns the total count of steps taken.

  8. Returning the Result: If the BFS does not find a connection, it signifies that the target cannot be reached without hitting a deadend, and therefore, it returns -1.

This is a clever use of bidirectional BFS to reduce the search space and improve efficiency, especially when the target is far from the initial state. The decision to move from one side is chosen based on the size of the queues, making the search strategy dynamic and adaptive to the states that have been already explored.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simplified example where the lock has only two wheels (for brevity) with digits from 0 to 9 and the following deadends: ["01", "10", "12"]. The target combination is "11".

Here is a step-by-step walkthrough using the solution approach:

  1. Deadend Preprocessing: First, we add all the deadends into a set s for quick look-up. If we attempt to generate any of these combinations, we will know instantly and avoid them.

  2. Handling Base Cases: The initial state is "00". Since this isn't a deadend and it isn't the target, we continue. The target "11" isn't the initial state, so we don't return 0. Also, "00" is not in the deadends set, so we don't return -1.

  3. Bidirectional BFS Initialization: We create two hash maps m1 and m2. m1 starts with {"00": 0} and m2 with {"11": 0} indicating the initial state and target each require 0 moves to reach from themselves. Also, two queues q1 and q2 are initialized containing "00" and "11", respectively.

  4. BFS with Two Queues: We alternate between the queues, starting with q1 (since both are the same size initially). In this example, q1 has fewer nodes most of the time.

  5. Generating Adjacent States: The next method generates new states by incrementing or decrementing the digits of the current state avoiding rolling over a deadend. So from "00" it generates "01" and "09" for the first wheel and "10" and "90" for the second wheel.

  6. Searching and Building Layers: However, since "01" and "10" are deadends, they are not added to the search queue. "09" and "90" would be added to m1.

  7. Reaching the Target: Since one of the generated states "90" upon decrement of the first wheel will convert to "80" which is not in m2 and is not a deadend, it will be added to q1. Similarly, from the target side, "11" will generate "21" and "01" for the first wheel and "10" and "12" for the second wheel. "01" and "10" are deadends and "12" is also a deadend, so only "21" is added to m2 and subsequently "20" and "22" from "21" which leads to "20" being enqueued. Notably, "20" is one step away from "00" and also one step away from "21" which was derived from the target "11".

Since "90" from q1 and "20" from q2 are adjacent on the lock (you can get from one to the other by a single move on the second wheel), when we increment the second wheel of "20", we find "20" in m1, indicating that the searches have met. m1['20'] contains the number of steps to get from "00" to "20" (which is 1 move), and m2['20'] contains the number of steps from "11" to "20" (also 1 move). Thus, the minimum number of moves to get to "11" from "00" without hitting a deadend is the sum of these two, which is 1 + 1 = 2.

  1. Returning the Result: Since we've found a connection, we return the total count of moves which is 2. If no connection were found and the queues were exhausted, we would return -1 to signify the target is not reachable without hitting a deadend.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def openLock(self, deadends: List[str], target: str) -> int:
6        # Function to generate the next possible combinations from current state
7        def get_next_states(state):
8            next_states = []
9            state_digits = list(state)
10            for i in range(4):
11                original_digit = state_digits[i]
12                # Decrement the digit (with wrap-around)
13                state_digits[i] = '9' if original_digit == '0' else str(int(original_digit) - 1)
14                next_states.append(''.join(state_digits))
15                # Increment the digit (with wrap-around)
16                state_digits[i] = '0' if original_digit == '9' else str(int(original_digit) + 1)
17                next_states.append(''.join(state_digits))
18                # Restore original digit for the next iteration
19                state_digits[i] = original_digit
20            return next_states
21
22        # Function to perform one step of bidirectional BFS
23        def extend(frontier, opposite_frontier, queue):
24            for _ in range(len(queue)):
25                current_state = queue.popleft()
26                current_step = frontier[current_state]
27                for next_state in get_next_states(current_state):
28                    if next_state in deadend_set or next_state in frontier:
29                        continue
30                    if next_state in opposite_frontier:
31                        return current_step + 1 + opposite_frontier[next_state]
32                    frontier[next_state] = current_step + 1
33                    queue.append(next_state)
34            return -1
35
36        # Main BFS function used for bidirectional search
37        def bidirectional_bfs():
38            start_frontier = {"0000": 0}  # Map of seen combinations starting from "0000"
39            target_frontier = {target: 0}  # Map of seen combinations starting from the target
40            start_queue = deque(['0000'])   # Queue for the BFS from "0000"
41            target_queue = deque([target])  # Queue for the BFS from the target
42
43            while start_queue and target_queue:
44                # Alternate between expanding from the start and target
45                result = extend(start_frontier, target_frontier, start_queue) if len(start_queue) <= len(target_queue) else extend(target_frontier, start_frontier, target_queue)
46                if result != -1:
47                    return result
48            return -1  # No solution found
49
50        # If the target is "0000", it's already unlocked
51        if target == '0000':
52            return 0
53        # Initialize dead end states in a set for quick lookup
54        deadend_set = set(deadends)
55        # If "0000" is in dead ends, we cannot start
56        if '0000' in deadend_set:
57            return -1
58        # Perform bidirectional BFS
59        return bidirectional_bfs()
60
61# Example usage:
62# solution = Solution()
63# min_turns = solution.openLock(["0201","0101","0102","1212","2002"], "0202")
64# print(min_turns) # This would output the minimum number of turns required to open the lock.
65
1class Solution {
2    private String startCombination; // Start combination for the lock
3    private String targetCombination; // Target combination to unlock
4    private Set<String> deadEnds = new HashSet<>(); // Set to store deadends
5
6    // Method to find the minimum number of moves to open the lock
7    public int openLock(String[] deadends, String target) {
8        startCombination = "0000";
9        this.targetCombination = target;
10
11        // Add all deadends to the set
12        Collections.addAll(this.deadEnds, deadends);
13      
14        // If the starting point is a deadend, we cannot proceed
15        if (this.deadEnds.contains(startCombination)) {
16            return -1;
17        }
18      
19        // If target is startCombination return 0 as no steps required
20        if (target.equals(startCombination)) {
21            return 0;
22        }
23
24        // Use bidirectional BFS to find the shortest path
25        return bidirectionalBfs();
26    }
27
28    // Helper method to perform bidirectional BFS search on the lock combinations
29    private int bidirectionalBfs() {
30        Map<String, Integer> visitedFromStart = new HashMap<>(); // Record steps from start
31        Map<String, Integer> visitedFromTarget = new HashMap<>(); // Record steps from target
32        Deque<String> queueFromStart = new ArrayDeque<>(); // Queue for BFS from start
33        Deque<String> queueFromTarget = new ArrayDeque<>(); // Queue for BFS from target
34
35        // Initialize the BFS from both ends
36        visitedFromStart.put(startCombination, 0);
37        visitedFromTarget.put(targetCombination, 0);
38        queueFromStart.offer(startCombination);
39        queueFromTarget.offer(targetCombination);
40
41        while (!queueFromStart.isEmpty() && !queueFromTarget.isEmpty()) {
42            // Always extend the smaller queue to optimize performance
43            int turns = queueFromStart.size() <= queueFromTarget.size() ?
44                        extendQueue(visitedFromStart, visitedFromTarget, queueFromStart) :
45                        extendQueue(visitedFromTarget, visitedFromStart, queueFromTarget);
46          
47            // If turns not equals to -1, a solution has been found
48            if (turns != -1) {
49                return turns;
50            }
51        }
52        return -1; // If no solution is found
53    }
54
55    // Expand the current level of the BFS search and check for intersections
56    private int extendQueue(Map<String, Integer> currentVisited, Map<String, Integer> oppositeVisited, Deque<String> currentQueue) {
57        int currentSize = currentQueue.size();
58        for (int i = 0; i < currentSize; ++i) {
59            String currentCombination = currentQueue.poll();
60            int currentStepCount = currentVisited.get(currentCombination);
61          
62            // Evaluate next possible combinations
63            for (String nextCombination : getNextCombinations(currentCombination)) {
64                // Skip if visited or is a dead end
65                if (currentVisited.containsKey(nextCombination) || deadEnds.contains(nextCombination)) {
66                    continue;
67                }
68
69                // If this combination has been reached from the opposite direction, return the total move count
70                if (oppositeVisited.containsKey(nextCombination)) {
71                    return currentStepCount + 1 + oppositeVisited.get(nextCombination);
72                }
73              
74                // Record the step count and add the new combination to the queue
75                currentVisited.put(nextCombination, currentStepCount + 1);
76                currentQueue.offer(nextCombination);
77            }
78        }
79        return -1;
80    }
81
82    // Generate all next possible lock combinations from a given combination
83    private List<String> getNextCombinations(String combination) {
84        List<String> nextCombinations = new ArrayList<>();
85        char[] chars = combination.toCharArray();
86      
87        for (int i = 0; i < 4; ++i) {
88            char originalChar = chars[i];
89          
90            // Turn the wheel one step forward
91            chars[i] = originalChar == '9' ? '0' : (char) (originalChar + 1);
92            nextCombinations.add(new String(chars));
93          
94            // Turn the wheel one step backwards
95            chars[i] = originalChar == '0' ? '9' : (char) (originalChar - 1);
96            nextCombinations.add(new String(chars));
97          
98            // Restore the original state for the next iteration
99            chars[i] = originalChar;
100        }
101      
102        return nextCombinations;
103    }
104}
105
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <unordered_map>
5#include <queue>
6using namespace std;
7
8class Solution {
9public:
10    unordered_set<string> deadendsSet;
11    string start;
12    string target;
13
14    // Tries to unlock the lock by turning the wheels,
15    // avoiding deadends and finding the shortest path to the target combination.
16    int openLock(vector<string>& deadends, string target) {
17        if (target == "0000") return 0;
18      
19        // Populating the deadends set for quick lookups.
20        for (const auto& d : deadends) deadendsSet.insert(d);
21        if (deadendsSet.count("0000")) return -1; // The start point is a deadend.
22      
23        this->start = "0000";
24        this->target = target;
25      
26        // Perform a bidirectional BFS to find the shortest path.
27        return bidirectionalBFS();
28    }
29
30    // Bidirectional BFS to find the shortest path to unlock the lock.
31    int bidirectionalBFS() {
32        unordered_map<string, int> m1; // Maps from string to minimum steps needed from start.
33        unordered_map<string, int> m2; // Maps from string to minimum steps needed from target.
34      
35        m1[start] = 0; // Initialize start
36        m2[target] = 0; // Initialize target
37      
38        queue<string> q1{{start}};
39        queue<string> q2{{target}};
40      
41        while (!q1.empty() && !q2.empty()) {
42            // Choose the queue with fewer elements to extend.
43            int t = (q1.size() <= q2.size()) ? extend(m1, m2, q1) : extend(m2, m1, q2);
44            if (t != -1) return t; // If a connection is found, return the number of steps.
45        }
46        return -1; // If no connection was found, return -1 indicating the lock cannot be unlocked.
47    }
48
49    // Extends the search from one queue, using the other queue to check for a meeting point.
50    int extend(unordered_map<string, int>& visitedFromOneSide, 
51               unordered_map<string, int>& visitedFromOtherSide,
52               queue<string>& queueToExtend) {
53        for (int n = queueToExtend.size(); n > 0; --n) {
54            string currentPosition = queueToExtend.front();
55            int step = visitedFromOneSide[currentPosition];
56            queueToExtend.pop();