752. Open the Lock

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();
57          
58            for (const string& nextPosition : getNextPositions(currentPosition)) {
59                if (deadendsSet.count(nextPosition) || visitedFromOneSide.count(nextPosition)) continue;
60                if (visitedFromOtherSide.count(nextPosition)) {
61                    // If we find the current nextPosition in the other side's visited map,
62                    // we found the shortest path.
63                    return step + 1 + visitedFromOtherSide[nextPosition];
64                }
65              
66                visitedFromOneSide[nextPosition] = step + 1; // Update the step count for the next position.
67                queueToExtend.push(nextPosition);
68            }
69        }
70        return -1;
71    }
72
73    // Generates all possible combinations that can be reached from the current state in one move.
74    vector<string> getNextPositions(string& currentPosition) {
75        vector<string> possibleNextPositions;
76        for (int i = 0; i < 4; ++i) {
77            char originalChar = currentPosition[i];
78
79            // Turn wheel down
80            currentPosition[i] = originalChar == '0' ? '9' : (char) (originalChar - 1);
81            possibleNextPositions.push_back(currentPosition);
82
83            // Turn wheel up
84            currentPosition[i] = originalChar == '9' ? '0' : (char) (originalChar + 1);
85            possibleNextPositions.push_back(currentPosition);
86
87            // Reset the character to the original one
88            currentPosition[i] = originalChar;
89        }
90        return possibleNextPositions;
91    }
92};
93

1// Imports go here in TypeScript, but these are C++ includes
2// and not applicable in TypeScript.
3
4// Defining the global variables for deadends, start, and target.
5let deadendsSet: Set<string> = new Set();
6let start: string = "0000";
7let target: string;
8
9// Tries to unlock the lock by turning the wheels,
10// avoiding deadends and finding the shortest path to the target combination.
11function openLock(deadends: string[], target: string): number {
12    if (target === "0000") return 0;
13
14    // Populating the deadends set for quick lookups.
15    deadendsSet = new Set(deadends);
16    if (deadendsSet.has("0000")) return -1; // The start point is a deadend.
17
18    // Set the global target for use in other functions.
19    target = target;
20
21    // Perform a bidirectional BFS to find the shortest path.
22    return bidirectionalBFS();
23}
24
25// Bidirectional BFS to find the shortest path to unlock the lock.
26function bidirectionalBFS(): number {
27    let m1: Map<string, number> = new Map(); // Maps from string to minimum steps needed from start.
28    let m2: Map<string, number> = new Map(); // Maps from string to minimum steps needed from target.
29
30    m1.set(start, 0); // Initialize start
31    m2.set(target, 0); // Initialize target
32
33    let q1: string[] = [start];
34    let q2: string[] = [target];
35
36    while (q1.length > 0 && q2.length > 0) {
37        // Choose the array with fewer elements to extend.
38        let steps = (q1.length <= q2.length) ? extend(m1, m2, q1) : extend(m2, m1, q2);
39        if (steps !== -1) return steps; // If a connection is found, return the number of steps.
40    }
41    return -1; // If no connection was found, return -1 indicating the lock cannot be unlocked.
42}
43
44// Extends the search from one queue, using the other queue to check for a meeting point.
45function extend(
46    visitedFromOneSide: Map<string, number>,
47    visitedFromOtherSide: Map<string, number>,
48    queueToExtend: string[]
49): number {
50    for (let i = queueToExtend.length - 1; i >= 0; i--) {
51        let currentPosition = queueToExtend.shift()!;
52        let step = visitedFromOneSide.get(currentPosition)!;
53
54        for (const nextPosition of getNextPositions(currentPosition)) {
55            if (deadendsSet.has(nextPosition) || visitedFromOneSide.has(nextPosition)) continue;
56          
57            if (visitedFromOtherSide.has(nextPosition)) {
58                // If we find the current nextPosition in the other side's visited map,
59                // we found the shortest path.
60                return step + 1 + visitedFromOtherSide.get(nextPosition)!;
61            }
62
63            visitedFromOneSide.set(nextPosition, step + 1); // Update the step count for the next position.
64            queueToExtend.push(nextPosition);
65        }
66    }
67    return -1;
68}
69
70// Generates all possible combinations that can be reached from the current state in one move.
71function getNextPositions(currentPosition: string): string[] {
72    let possibleNextPositions: string[] = [];
73    for (let i = 0; i < 4; ++i) {
74        let originalChar = currentPosition[i];
75
76        // Using charCodeAt to get the numeric ASCII value and String.fromCharCode to return to a string character after incrementing/decrementing.
77        // Turn wheel down
78        currentPosition =
79            currentPosition.substring(0, i) +
80            (originalChar === '0' ? '9' : String.fromCharCode(originalChar.charCodeAt(0) - 1)) +
81            currentPosition.substring(i + 1);
82        possibleNextPositions.push(currentPosition);
83
84        // Turn wheel up
85        currentPosition =
86            currentPosition.substring(0, i) +
87            (originalChar === '9' ? '0' : String.fromCharCode(originalChar.charCodeAt(0) + 1)) +
88            currentPosition.substring(i + 1);
89        possibleNextPositions.push(currentPosition);
90
91        // The current character is left unchanged because it's always overwritten in this implementation.
92    }
93    return possibleNextPositions;
94}
95