BFS 算法解题套路框架
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 111. Minimum Depth of Binary Tree | 🟢 |
| 752. Open the Lock | 🟠 |
Prerequisites
Before reading this article, you should first learn:
Tip
本文有视频版：BFS Algorithm Core Framework。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
Many people have asked about the BFS and DFS frameworks in the background, so let's talk about them today.
First, if you say you haven't written a BFS framework, that's true, but today we'll write one and you just need to memorize it. However, if you say you haven't written a DFS framework, then you're mistaken. Actually, DFS is essentially backtracking. We've covered this in a previous article Backtracking Algorithm Framework Detailed Explanation, and it's very well written, so I recommend reviewing it thoroughly, hehehe~
The core idea of BFS should be easy to understand. It's about abstracting problems into graphs, starting from a point, and spreading out in all directions. Generally, we use a "queue" data structure to write BFS algorithms, adding all nodes around a node to the queue each time.
The main difference between BFS and DFS is: BFS always finds the shortest path, but the trade-off is that its space complexity can be much higher than DFS. The reason for this will become clear after we introduce the framework.
In this article, we'll go from simple to complex and solve two typical BFS problems: "Minimum Height of a Binary Tree" and "Minimum Steps to Open a Password Lock." We'll guide you step-by-step on how to write BFS algorithms.
I. Algorithm Framework
To talk about frameworks, let's first illustrate common scenarios where BFS (Breadth-First Search) appears. Essentially, the core of the problem is to find the shortest distance from a starting point start to a target point target in a 'graph'. This example might sound dull, but BFS algorithm problems fundamentally revolve around this task. Once you grasp this dry essence, you can confidently tackle various problem presentations.
This broad description can have many variations. For instance, navigating a maze where some cells are walls and you can't pass through. What's the shortest distance from the start to the end? What if this maze includes 'teleportation portals' that instantly transport you?
Another example is transforming one word into another by replacing characters, with only one character change allowed per step. What's the minimum number of replacements needed?
Or consider the game of "连连看" (Match-3), where two blocks are eliminated not only if their patterns match but also if the shortest connecting line between them has no more than two bends. How does the game determine the number of bends in the shortest line when you click two coordinates?
And so on...
Despite the variety, fundamentally, these problems are all the same: you have a 'graph', a starting point, and an endpoint, and you need to find the shortest path. That's the essence of BFS. Once you understand the framework, you can write it down effortlessly.
Just remember the following framework, and you're good to go:
// Calculate the shortest distance from the start point to the target point
int BFS(Node start, Node target) {
// Core data structure
Queue<Node> q;
// Avoid taking detours
Set<Node> visited;
// Add the start point to the queue
q.offer(start);
visited.add(start);
while (q not empty) {
int sz = q.size();
// Spread all nodes in the current queue to their surroundings
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
// Highlight: Here we check if we've reached the target
if (cur is target)
return step;
// Add the adjacent nodes of cur to the queue
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
}
// If it reaches here, it means the target node is not found in the graph
}int BFS(Node start, Node target) {
queue<Node> q;
set<Node> visited;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node cur = q.front();
q.pop();
if (cur == target)
return step;
for (Node x : cur.adj()) {
if (visited.count(x) == 0) {
q.push(x);
visited.insert(x);
}
}
}
}
// if it reaches here, it means the target node was not found in the graph
}from typing import List, Set
from collections import deque
class Node:
def __init__(self, val: int):
self.val = val
self.neighbors = []
def BFS(start: Node, target: Node) -> int:
# the core data structure
q = deque()
# avoid taking the wrong path back
visited = set()
# add the start node to the queue
q.append(start)
visited.add(start)
# record the number of steps of spread
step = 0
while q:
step += 1
size = len(q)
# spread all nodes in the current queue to their neighbors
for i in range(size):
cur = q.popleft()
# highlight: here we check if we've reached the target
if cur == target:
return step
# add the neighbors of cur to the queue
for x in cur.neighbors:
if x not in visited:
q.append(x)
visited.add(x)
# if it reaches here, it means the target node is not found in the graph
return -1// Calculate the shortest distance from the start point to the target point
func BFS(start Node, target Node) int {
// core data structure
q := make([]Node, 0)
// avoid taking detours
visited := make(map[Node]bool)
// add the start point to the queue
q = append(q, start)
visited[start] = true
for len(q) > 0 {
sz := len(q)
// spread all nodes in the current queue to their neighbors
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
// highlight: here we check if we have reached the target
if cur == target {
return step
}
// add the adjacent nodes of cur to the queue
for _, x := range cur.adj() {
if _, ok := visited[x]; !ok {
q = append(q, x)
visited[x] = true
}
}
}
}
// if it reaches here, it means the target node was not found in the graph
}var BFS = function(start, target) {
// core data structure
var q = [];
// avoid going back
var visited = new Set();
var step = 0;
// add the start point to the queue
q.push(start);
visited.add(start);
while (q.length > 0) {
var sz = q.length;
// spread all nodes in the current queue to their neighbors
for (var i = 0; i < sz; i++) {
var cur = q.shift();
// highlight: here we determine if we have reached the target
if (cur == target)
return step;
// add the adjacent nodes of cur to the queue
var adj = cur.adj();
for (var j = 0; j < adj.length; j++) {
var x = adj[j];
if (!visited.has(x)) {
q.push(x);
visited.add(x);
}
}
}
step++;
}
// if it reaches here, it means the target node was not found in the graph
}Let's not elaborate on the queue q, as it is the core data structure for BFS; cur.adj() generally refers to the nodes adjacent to cur. For example, in a 2D array, the positions above, below, to the left, and to the right of cur are adjacent nodes. The main role of visited is to prevent backtracking, which is usually necessary. However, in structures like a typical binary tree, where child nodes do not have pointers to parent nodes, visited is not needed as there is no risk of backtracking.
II. Minimum Height of a Binary Tree
Let's start with a simple problem to practice the BFS framework: determining the minimum height of a binary tree. This is also LeetCode problem #111, "Minimum Depth of Binary Tree":
111. Minimum Depth of Binary Tree | 力扣 | LeetCode |
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6] Output: 5
Constraints:
- The number of nodes in the tree is in the range
[0, 105]. -1000 <= Node.val <= 1000
How do we fit this into the BFS framework? First, clarify what the starting point start and the ending point target are, and how to determine when the target is reached.
Obviously, the starting point is the root node, and the target is the leaf node closest to the root. A leaf node is one where both child nodes are null:
if (cur.left == null && cur.right == null)
// reach the leaf nodeSo, by slightly modifying our framework mentioned above, we can write the solution:
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// the root itself is a level, initialize depth to 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
// spread all nodes in the current queue to their neighbors
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// determine if the end point is reached
if (cur.left == null && cur.right == null)
return depth;
// add the adjacent nodes of cur to the queue
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
// increase the step count here
depth++;
}
return depth;
}
}class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> q;
q.push(root);
// the root itself is a level, initialize depth to 1
int depth = 1;
while (!q.empty()) {
int sz = q.size();
// spread all nodes in the current queue to their surroundings
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
// determine if we have reached the end
if (cur->left == nullptr && cur->right == nullptr)
return depth;
// add the adjacent nodes of cur to the queue
if (cur->left != nullptr)
q.push(cur->left);
if (cur->right != nullptr)
q.push(cur->right);
}
// increase the step count here
depth++;
}
return depth;
}
};class Solution:
def minDepth(self, root):
if not root:
return 0
queue = deque()
queue.append(root)
# the root itself is a level, initialize depth to 1
depth = 1
while queue:
sz = len(queue)
# spread all nodes in the current queue to their surroundings
for i in range(sz):
cur = queue.popleft()
# determine if the end is reached
if not cur.left and not cur.right:
return depth
# add the adjacent nodes of cur to the queue
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
# increase the step count here
depth += 1
return depthfunc minDepth(root *TreeNode) int {
if root == nil {
return 0
}
var q []*TreeNode
q = append(q, root)
// the root itself is a level, initialize depth to 1
depth := 1
for len(q) != 0 {
sz := len(q) // Get current queue size
// spread all nodes in the current queue to their neighbors
for i := 0; i < sz; i++ {
cur := q[0] // Get the first element
q = q[1:] // Dequeue
// determine if we've reached the end
if cur.Left == nil && cur.Right == nil {
return depth
}
// add the neighboring nodes of cur to the queue
if cur.Left != nil {
q = append(q, cur.Left)
}
if cur.Right != nil {
q = append(q, cur.Right)
}
}
// Increase the depth at each BFS level
depth++
}
return depth
}var minDepth = function(root){
if(root == null) return 0;
let queue = [];
queue.push(root);
// the root itself is a level, initialize depth to 1
let depth = 1;
while(queue.length != 0){
let size = queue.length;
// spread all nodes in the current queue to their surroundings
for(let i = 0; i < size; i++){
let cur = queue.shift();
// determine if the end is reached
if(cur.left == null && cur.right == null)
return depth;
// add the adjacent nodes of cur to the queue
if(cur.left != null)
queue.push(cur.left);
if(cur.right != null)
queue.push(cur.right);
}
// increase the step count here
depth++;
}
return depth;
}Pay attention to the coordination between the while loop and the for loop here. The while loop controls moving down layer by layer, and the for loop uses the sz variable to traverse each layer of the binary tree nodes from left to right:
This point is crucial. This pattern is common in typical BFS problems. However, in the Dijkstra Algorithm Template Framework, we modify this code pattern. After reading and understanding this article, you can see how the BFS algorithm evolves into Dijkstra's algorithm for finding the shortest path in weighted graphs.
Speaking of binary trees, they are quite simple data structures. I believe you can understand the above code. In fact, other complex problems are just variations of this framework. Before diving into complex issues, let's answer two questions:
1. Why can BFS find the shortest distance, but DFS cannot?
First, look at the logic of BFS. Each time depth increases, all nodes in the queue move one step forward. This ensures that the first time you reach the destination, the number of steps taken is the minimum.
Can DFS find the shortest path? Technically, yes, but the time complexity is much higher. Think about it: DFS relies on the recursive stack to record the path taken. To find the shortest path, you would have to explore all branches of the binary tree to compare the lengths of the paths, right? BFS, on the other hand, uses a queue to move "in unison" one step at a time, allowing it to find the shortest distance without traversing the entire tree.
To put it simply, DFS is like a line, while BFS is like a surface; DFS is a solo effort, whereas BFS is a group action. This should be relatively easy to understand.
2. If BFS is so good, why does DFS still exist?
BFS can find the shortest distance, but it has a higher space complexity. DFS, however, has a lower space complexity.
Take the example of the binary tree problem we just discussed. Suppose you have a full binary tree with N nodes. For the DFS algorithm, the space complexity is essentially the recursive stack, which, in the worst case, is the height of the tree, i.e., O(logN).
But consider the BFS algorithm. The queue will always store the nodes of one layer of the binary tree at a time. In the worst case, the space complexity would be the number of nodes at the bottom layer of the tree, which is N/2, or O(N) in Big O notation.
Thus, BFS comes with a cost. Generally, BFS is used when finding the shortest path, while DFS is more commonly used in other scenarios (mainly because recursive code is easier to write).
Alright, now that you have a good understanding of BFS, let's tackle a more challenging problem to deepen your understanding of the framework.
Three: Minimum Number of Attempts to Unlock a Password
This is LeetCode problem 752, "Open the Lock," which is quite interesting:
752. Open the Lock | 力扣 | LeetCode |
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
Input: deadends = ["8888"], target = "0009" Output: 1 Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Explanation: We cannot reach the target without getting stuck.
Constraints:
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4- target will not be in the list
deadends. targetanddeadends[i]consist of digits only.
The function signature is as follows:
int openLock(String[] deadends, String target)int openLock(vector<string>& deadends, string target)def openLock(deadends: List[str], target: str) -> intfunc openLock(deadends []string, target string) int {}var openLock = function(deadends, target) {
}The problem describes the kind of password lock commonly seen in our daily life. If there were no constraints, the minimum number of turns would be easy to calculate, just like how we usually open a password lock by directly turning to the password.
However, the challenge now is that we cannot encounter deadends. How should we calculate the minimum number of turns?
Step 1: Ignore all constraints, including deadends and target, and think about one question: If you were to design an algorithm to enumerate all possible password combinations, how would you do it?
Enumerate, of course. To make it simpler, if you only turn the lock once, how many possibilities are there? There are 4 positions, and each position can be turned up or down, which means there are 8 possibilities, right?
For example, starting from "0000", turning once can enumerate the passwords "1000", "9000", "0100", "0900"... totaling 8 combinations. Then, using these 8 passwords as a base, turn each one again to enumerate all possible combinations...
Think carefully, this can be abstracted into a graph where each node has 8 adjacent nodes. Since you need to find the shortest distance, this is a typical BFS problem. The framework can be put to use. First, write a 'primitive' BFS framework code before discussing anything else:
// increment s[j] by one
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// decrement s[j] by one
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
// BFS framework to print out all possible passwords
void BFS(String target) {
Queue<String> q = new LinkedList<>();
q.offer("0000");
while (!q.isEmpty()) {
int sz = q.size();
// spread all nodes in the current queue to their neighbors
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// determine if the end point is reached
System.out.println(cur);
// add the neighbors of a node to the queue
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
String down = minusOne(cur, j);
q.offer(up);
q.offer(down);
}
}
// increase the step count here
}
return;
}// increment s[j] by one
string plusOne(string s, int j) {
char ch[s.length()];
strcpy(ch, s.c_str());
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
string res(ch);
return res;
}
// decrement s[i] by one
string minusOne(string s, int j) {
char ch[s.length()];
strcpy(ch, s.c_str());
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
string res(ch);
return res;
}
// BFS framework to print out all possible passwords
void BFS(string target) {
queue<string> q;
q.push("0000");
while (!q.empty()) {
int sz = q.size();
// spread all nodes in the current queue
for (int i = 0; i < sz; i++) {
string cur = q.front(); q.pop();
// determine if we have reached the target
cout << cur << endl;
// add adjacent nodes of a node to the queue
for (int j = 0; j < 4; j++) {
string up = plusOne(cur, j);
string down = minusOne(cur, j);
q.push(up);
q.push(down);
}
}
// increment the step count here
}
return;
}from typing import List
# increment s[j] by one
def plusOne(s: str, j: int) -> str:
ch = list(s)
if ch[j] == '9':
ch[j] = '0'
else:
ch[j] = chr(ord(ch[j]) + 1)
return ''.join(ch)
# decrement s[j] by one
def minusOne(s: str, j: int) -> str:
ch = list(s)
if ch[j] == '0':
ch[j] = '9'
else:
ch[j] = chr(ord(ch[j]) - 1)
return ''.join(ch)
# BFS framework to print all possible passwords
def BFS(target: str) -> None:
q = ['0000']
while len(q) > 0:
sz = len(q)
# spread all nodes in the current queue to their neighbors
for i in range(sz):
cur = q.pop(0)
# determine if the end point is reached
print(cur)
# add the neighbors of a node to the queue
for j in range(4):
up = plusOne(cur, j)
down = minusOne(cur, j)
q.append(up)
q.append(down)
# increment the step count here
return// turn s[j] up by one
func plusOne(s string, j int) string {
ch := []byte(s)
if ch[j] == '9' {
ch[j] = '0'
} else {
ch[j] += 1
}
return string(ch)
}
// turn s[i] down by one
func minusOne(s string, j int) string {
ch := []byte(s)
if ch[j] == '0' {
ch[j] = '9'
} else {
ch[j] -= 1
}
return string(ch)
}
// BFS framework, print out all possible passwords
func BFS(target string) {
var q []string
q = append(q, "0000")
for len(q) > 0 {
sz := len(q)
// spread all nodes in the current queue to their neighbors
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
// determine if we have reached the destination
fmt.Println(cur)
// add a node's neighbors to the queue
for j := 0; j < 4; j++ {
up := plusOne(cur, j)
down := minusOne(cur, j)
q = append(q, up, down)
}
}
// increment the step count here
}
return
}// increment s[j] by one
var plusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '9') ch[j] = '0';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) + 1);
return ch.join('');
};
// decrement s[i] by one
var minusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '0') ch[j] = '9';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) - 1);
return ch.join('');
}
// BFS framework to print out all possible passwords
var BFS = function(target) {
let q = ['0000'];
while(q.length > 0) {
let sz = q.length;
// spread all nodes in the current queue to their neighbors
for(let i = 0; i < sz; i++) {
let cur = q.shift();
// determine if the end is reached
console.log(cur);
// add the neighboring nodes of a node to the queue
for(let j = 0; j < 4; j++) {
let up = plusOne(cur, j);
let down = minusOne(cur, j);
q.push(up)
q.push(down)
}
}
// increment the step count here
}
return;
}注
This code certainly has many issues, but solving algorithm problems is never a one-step process; it's about evolving from rough to perfect. Let's not be perfectionists and take it slow, okay?
This BFS code can already enumerate all possible password combinations, but it obviously can't solve the problem as is. Here are the issues that need to be addressed:
It can go back to where it started. For example, if we dial from
"0000"to"1000", when we take"1000"out of the queue, we might dial back to"0000". This can lead to an infinite loop.There is no termination condition. According to the problem, we should stop and return the number of moves once we find the
target.There is no handling of
deadends. These "dead passwords" should not appear, meaning you need to skip them when encountered.
If you can understand the code above, you really deserve a round of applause. Just make a few modifications in the corresponding places within the BFS framework to fix these issues:
class Solution {
public int openLock(String[] deadends, String target) {
// record the deadends that need to be skipped
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// record the passwords that have been exhausted to prevent backtracking
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// start breadth-first search from the starting point
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int sz = q.size();
// spread all nodes in the current queue to their surroundings
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// determine if the end is reached
if (deads.contains(cur))
continue;
if (cur.equals(target))
return step;
// add the unvisited adjacent nodes of a node to the queue
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
// increment the step count here
step++;
}
// if the target password is not found after exhaustion, then it is not found
return -1;
}
// turn s[j] up once
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// turn s[i] down once
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
// record the deadends that need to be skipped
unordered_set<string> deads(deadends.begin(), deadends.end());
// record the passwords that have been exhausted to prevent backtracking
unordered_set<string> visited;
queue<string> q;
// start breadth-first search from the starting point
int step = 0;
q.push("0000");
visited.insert("0000");
while (!q.empty()) {
int sz = q.size();
// spread all nodes in the current queue to their surroundings
for (int i = 0; i < sz; i++) {
string cur = q.front(); q.pop();
// determine if the end point is reached
if (deads.count(cur))
continue;
if (cur == target)
return step;
// add the unvisited adjacent nodes of a node to the queue
for (int j = 0; j < 4; j++) {
string up = plusOne(cur, j);
if (!visited.count(up)) {
q.push(up);
visited.insert(up);
}
string down = minusOne(cur, j);
if (!visited.count(down)) {
q.push(down);
visited.insert(down);
}
}
}
// increment the step count here
step++;
}
// if the target password is not found after exhaustive search, then it is not found
return -1;
}
// turn s[j] up once
string plusOne(string s, int j) {
s[j] = s[j] == '9' ? '0' : s[j] + 1;
return s;
}
// turn s[i] down once
string minusOne(string s, int j) {
s[j] = s[j] == '0' ? '9' : s[j] - 1;
return s;
}
};class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
# record the deadends that need to be skipped
deads = set(deadends)
# record the passwords that have been exhausted to prevent backtracking
visited = set()
q = collections.deque()
# start breadth-first search from the starting point
step = 0
q.append("0000")
visited.add("0000")
while q:
sz = len(q)
# spread all nodes in the current queue to their neighbors
for _ in range(sz):
cur = q.popleft()
# determine if it has reached the end point
if cur in deads:
continue
if cur == target:
return step
# add the unvisited adjacent nodes of a node to the queue
for j in range(4):
up = self.plusOne(cur, j)
if up not in visited:
q.append(up)
visited.add(up)
down = self.minusOne(cur, j)
if down not in visited:
q.append(down)
visited.add(down)
# increment the step count here
step += 1
# if the target password is not found after exhaustion, it is not found
return -1
# turn s[j] up once
def plusOne(self, s: str, j: int) -> str:
ch = list(s)
if ch[j] == '9':
ch[j] = '0'
else:
ch[j] = str(int(ch[j]) + 1)
return ''.join(ch)
# turn s[i] down once
def minusOne(self, s: str, j: int) -> str:
ch = list(s)
if ch[j] == '0':
ch[j] = '9'
else:
ch[j] = str(int(ch[j]) - 1)
return ''.join(ch)func openLock(deadends []string, target string) int {
// record the deadends that need to be skipped
deads := make(map[string]bool)
for _, s := range deadends {
deads[s] = true
}
// record the passwords that have been exhausted to prevent backtracking
visited := make(map[string]bool)
q := make([]string, 0)
// start breadth-first search from the starting point
step := 0
q = append(q, "0000")
visited["0000"] = true
for len(q) != 0 {
sz := len(q)
// spread all nodes in the current queue to their neighbors
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
// determine if the end point is reached
if deads[cur] {
continue
}
if cur == target {
return step
}
// add the unvisited neighboring nodes of a node to the queue
for j := 0; j < 4; j++ {
up := plusOne(cur, j)
if !visited[up] {
q = append(q, up)
visited[up] = true
}
down := minusOne(cur, j)
if !visited[down] {
q = append(q, down)
visited[down] = true
}
}
}
// increment the step count here
step++
}
// if the target password is not found after exhaustive search, it's not found
return -1
}
// turn s[j] up once
func plusOne(s string, j int) string {
ch := []byte(s)
if ch[j] == '9' {
ch[j] = '0'
} else {
ch[j] += 1
}
return string(ch)
}
// turn s[i] down once
func minusOne(s string, j int) string {
ch := []byte(s)
if ch[j] == '0' {
ch[j] = '9'
} else {
ch[j] -= 1
}
return string(ch)
}var openLock = function(deadends, target) {
// record the deadends that need to be skipped
let deads = new Set(deadends);
// record the passwords that have been exhausted to prevent backtracking
let visited = new Set();
let q = [];
// start breadth-first search from the starting point
let step = 0;
q.push("0000");
visited.add("0000");
while (q.length !== 0) {
let sz = q.length;
// spread all nodes in the current queue to their neighbors
for (let i = 0; i < sz; i++) {
let cur = q.shift();
// determine if the end is reached
if (deads.has(cur))
continue;
if (cur === target)
return step;
// add the unvisited neighboring nodes of a node to the queue
for (let j = 0; j < 4; j++) {
let up = plusOne(cur, j);
if (!visited.has(up)) {
q.push(up);
visited.add(up);
}
let down = minusOne(cur, j);
if (!visited.has(down)) {
q.push(down);
visited.add(down);
}
}
}
// increment the step count here
step++;
}
// if the target password is not found after exhaustive search, then it's not found
return -1;
}
// turn s[j] up once
var plusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '9') ch[j] = '0';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) + 1);
return ch.join('');
};
// turn s[i] down once
var minusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '0') ch[j] = '9';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) - 1);
return ch.join('');
}With this, we have solved the problem. There's a minor optimization: you can do without the dead hash set. Instead, you can initialize these elements directly into the visited set, which achieves the same effect and might be more elegant.
Four, Bidirectional BFS Optimization
Do you think the BFS algorithm ends here? On the contrary. There's a slightly more advanced optimization approach for BFS: Bidirectional BFS, which can further improve the efficiency of the algorithm.
Due to space limitations, I'll just mention the difference here: Traditional BFS starts from the beginning and spreads out in all directions, stopping when it reaches the end; whereas Bidirectional BFS starts from both the beginning and the end, stopping when there is an intersection.
Why does this improve efficiency? Actually, if you analyze the algorithm complexity using Big O notation, both have a worst-case complexity of O(N). However, in practice, Bidirectional BFS is indeed faster. Let me show you two diagrams to illustrate:
In the tree structure shown in the diagrams, if the target is at the bottom, traditional BFS would search through all the nodes of the tree to find the target. In contrast, Bidirectional BFS only needs to traverse half the tree to find an intersection, which means it finds the shortest path. From this example, you can intuitively see that Bidirectional BFS is more efficient than traditional BFS.
However, Bidirectional BFS has its limitations, as you must know where the end point is. For example, in the binary tree minimum height problem we discussed earlier, you don't know where the end point is at the beginning, so you can't use Bidirectional BFS. But for the second password lock problem, you can use Bidirectional BFS to improve efficiency with some minor code modifications:
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// Use a set instead of a queue to quickly determine if an element exists
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int step = 0;
q1.add("0000");
q2.add(target);
while (!q1.isEmpty() && !q2.isEmpty()) {
// The hash set cannot be modified during traversal, use temp to store the diffusion results
Set<String> temp = new HashSet<>();
// Spread all nodes in q1 to their neighbors
for (String cur : q1) {
// Determine if the end point is reached
if (deads.contains(cur))
continue;
if (q2.contains(cur))
return step;
visited.add(cur);
// Add an unvisited neighboring node of a node to the set
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up))
temp.add(up);
String down = minusOne(cur, j);
if (!visited.contains(down))
temp.add(down);
}
}
// Increment the step count here
step++;
// temp is equivalent to q1
// Swap q1 and q2 here, the next while loop will spread q2
q1 = q2;
q2 = temp;
}
return -1;
}
// Turn s[j] up once
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// Turn s[i] down once
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
}class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> deads(deadends.begin(), deadends.end());
// use a set instead of a queue for quick element existence check
unordered_set<string> q1, q2, visited;
int step = 0;
q1.insert("0000");
q2.insert(target);
while (!q1.empty() && !q2.empty()) {
// the hash set cannot be modified during traversal, use temp to store the spread results
unordered_set<string> temp;
// spread all nodes in q1 to their neighbors
for (const string& cur : q1) {
// determine if the end point is reached
if (deads.count(cur))
continue;
if (q2.count(cur))
return step;
visited.insert(cur);
// add an unvisited neighboring node of a node to the set
for (int j = 0; j < 4; j++) {
string up = plusOne(cur, j);
if (!visited.count(up))
temp.insert(up);
string down = minusOne(cur, j);
if (!visited.count(down))
temp.insert(down);
}
}
// increment the step count here
step++;
// temp is equivalent to q1
// swap q1 and q2 here, the next while loop will spread q2
q1 = q2;
q2 = temp;
}
return -1;
}
private:
string plusOne(string s, int j) {
if (s[j] == '9')
s[j] = '0';
else
s[j] += 1;
return s;
}
string minusOne(string s, int j) {
if (s[j] == '0')
s[j] = '9';
else
s[j] -= 1;
return s;
}
};class Solution:
def openLock(self, deadends: list[str], target: str) -> int:
deads = set(deadends)
# use a set instead of a queue for quick membership testing
q1 = set()
q2 = set()
visited = set()
step = 0
q1.add("0000")
q2.add(target)
while q1 and q2:
# the hash set cannot be modified during traversal, use temp to store the diffusion results
temp = set()
# spread all nodes in q1 to their neighbors
for cur in q1:
# determine if the end is reached
if cur in deads:
continue
if cur in q2:
return step
visited.add(cur)
# add the unvisited neighboring nodes of a node to the set
for j in range(4):
up = self.plusOne(cur, j)
if up not in visited:
temp.add(up)
down = self.minusOne(cur, j)
if down not in visited:
temp.add(down)
# increment the step count here
step += 1
# temp is equivalent to q1
# swap q1 and q2 here, the next while loop will spread q2
q1 = q2
q2 = temp
return -1
def plusOne(self, cur: str, j: int) -> str:
ch = list(cur)
if ch[j] == '9':
ch[j] = '0'
else:
ch[j] = str(int(ch[j]) + 1)
return ''.join(ch)
def minusOne(self, cur: str, j: int) -> str:
ch = list(cur)
if ch[j] == '0':
ch[j] = '9'
else:
ch[j] = str(int(ch[j]) - 1)
return ''.join(ch)import (
"strings"
)
func openLock(deadends []string, target string) int {
deads := make(map[string]bool)
for _, s := range deadends {
deads[s] = true
}
// use a set instead of a queue for quick existence check
q1 := make(map[string]bool)
q2 := make(map[string]bool)
visited := make(map[string]bool)
step := 0
q1["0000"] = true
q2[target] = true
for len(q1) > 0 && len(q2) > 0 {
// the hash set cannot be modified during traversal, use temp to store the spread results
temp := make(map[string]bool)
// spread all nodes in q1 to their neighbors
for cur := range q1 {
// check if it has reached the end
if deads[cur] {
continue
}
if q2[cur] {
return step
}
visited[cur] = true
// add an unvisited neighboring node of a node to the set
for j := 0; j < 4; j++ {
up := plusOne(cur, j)
if !visited[up] {
temp[up] = true
}
down := minusOne(cur, j)
if !visited[down] {
temp[down] = true
}
}
}
// increment the step count here
step++
// temp is equivalent to q1
// swap q1 and q2 here, the next while loop will spread q2
q1 = q2
q2 = temp
}
return -1
}
func plusOne(s string, j int) string {
ch := []rune(s)
if ch[j] == '9' {
ch[j] = '0'
} else {
ch[j]++
}
return string(ch)
}
func minusOne(s string, j int) string {
ch := []rune(s)
if ch[j] == '0' {
ch[j] = '9'
} else {
ch[j]--
}
return string(ch)
}var openLock = function(deadends, target) {
let deads = new Set(deadends);
// Use a set instead of a queue for quick existence check
let q1 = new Set(["0000"]);
let q2 = new Set([target]);
let visited = new Set();
let step = 0;
while (q1.size > 0 && q2.size > 0) {
// Cannot modify hash set during traversal, use temp to store the spread results
let temp = new Set();
// Spread all nodes in q1 to their neighbors
for (let cur of q1) {
// Check if it reaches the end
if (deads.has(cur)) {
continue;
}
if (q2.has(cur)) {
return step;
}
visited.add(cur);
// Add an unvisited neighboring node of a node to the set
for (let j = 0; j < 4; j++) {
let up = plusOne(cur, j);
if (!visited.has(up)) {
temp.add(up);
}
let down = minusOne(cur, j);
if (!visited.has(down)) {
temp.add(down);
}
}
}
// Increment the step count here
step++;
// Temp is equivalent to q1
// Swap q1 and q2 here, the next while loop will spread q2
q1 = q2;
q2 = temp;
}
return -1;
};
var plusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '9') ch[j] = '0';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) + 1);
return ch.join('');
};
var minusOne = function(s, j) {
let ch = s.split('');
if(ch[j] == '0') ch[j] = '9';
else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) - 1);
return ch.join('');
}Bidirectional BFS still follows the BFS algorithm framework, but instead of using queues, it uses HashSet to quickly determine if there is an intersection between two sets.
Another key technique is to swap the contents of q1 and q2 at the end of the while loop, so by default expanding q1 is equivalent to alternately expanding q1 and q2.
In fact, there is another optimization for bidirectional BFS, which is to make a judgment at the beginning of the while loop:
// ...
while (!q1.isEmpty() && !q2.isEmpty()) {
if (q1.size() > q2.size()) {
// swap q1 and q2
temp = q1;
q1 = q2;
q2 = temp;
}
// ...
}// ...
while (!q1.empty() && !q2.empty()) {
if (q1.size() > q2.size()) {
// swap q1 and q2
queue<int> temp = q1;
q1 = q2;
q2 = temp;
}
// ...
}# ...
while not q1.empty() and not q2.empty():
if q1.qsize() > q2.qsize():
# swap q1 and q2
temp = q1
q1 = q2
q2 = temp
# ...// ...
for !q1.isEmpty() && !q2.isEmpty() {
if q1.size() > q2.size() {
// swap q1 and q2
temp := q1
q1 = q2
q2 = temp
}
// ...
}// ...
while (!q1.isEmpty() && !q2.isEmpty()) {
if (q1.size() > q2.size()) {
// swap q1 and q2
var temp = q1;
q1 = q2;
q2 = temp;
}
// ...
}Why is this an optimization?
According to the logic of BFS, the more elements in the queue (set), the more elements there will be in the new queue (set) after expansion. In bidirectional BFS, if we always choose a smaller set to expand, the space growth rate will be slower, and the efficiency will be higher.
However, it's important to note that whether it's traditional BFS or bidirectional BFS, and regardless of whether optimizations are applied, the time complexity remains the same when measured by Big O standards. Bidirectional BFS can be considered a trick that makes the algorithm run a bit faster, but mastering it is not essential. The most crucial part is to remember the general BFS framework, as all BFS algorithms can be solved using it.
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
