752. Open the Lock
Tags:
Medium
Skills:
BFSBidirectional BFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
deadends: Danh sách các trạng thái mà nếu ổ khóa rơi vào, bạn sẽ không thể tiếp tục xoay.Phân tích bài toán
Time and space complexity
| Method | Time Complexity | Space Complexity | Notes |
| BFS | O(4*(10^4+D)) | O(4*(10^4+D)) | Simpler to implement but may explore more states. |
| Bidirectional BFS | O(4*(10^4+D)) | O(4*(10^4+D)) | Faster in practice due to reduced search space (approximately halved). |
D: is a size of deadends
Solution - Solid BFS
1function openLock(deadends: string[], target: string): number {
2 function getNeighbors(node: string): string[] {
3 const neighbors: string[] = []
4 for (let i = 0; i < 4; i++) {
5 const digit = parseInt(node[i]);
6 const wheel_up = node.slice(0, i) + ((digit + 1) % 10) + node.slice(i + 1)
7 const wheel_down = node.slice(0, i) + ((digit + 9) % 10) + node.slice(i + 1)
8
9 // wheel up
10 neighbors.push(wheel_up);
11
12 // wheel down
13 neighbors.push(wheel_down);
14 }
15 return neighbors;
16 }
17
18 const start = "0000"
19 const dead_set: Set<string> = new Set(deadends);
20 if (dead_set.has(start)) return -1;
21
22 const queue: [string, number][] = [[start, 0]]
23 const visisted: Set<string> = new Set();
24 visisted.add(start);
25
26 while (queue.length > 0) {
27 const [current, steps] = queue.shift()!;
28 if (current === target) return steps;
29
30 const neighbors = getNeighbors(current);
31 for (const neighbor of neighbors) {
32 if (!visisted.has(neighbor) && !dead_set.has(neighbor)) {
33 visisted.add(neighbor);
34 queue.push([neighbor, steps + 1]);
35 }
36 }
37 }
38
39 return -1;
40};