BFS Algorithm Common Patterns and Code Template

Many people have asked about the frameworks for BFS and DFS, so let's talk about them today.

First, if you say you've never written a BFS framework, that's fine. I'll write one today, and you just need to memorize it. But if you say you've never written a DFS framework, you're mistaken. DFS algorithms are essentially backtracking algorithms. We've already covered this in the previous article Detailed Explanation of the Backtracking Algorithm Framework, and it's written quite well. I recommend you review it thoroughly.

The core idea of BFS (Breadth-First Search) is not difficult to understand. It involves abstracting some problems into graphs and starting from one point to spread outwards. Typically, we use a "queue" data structure to implement BFS algorithms, adding all neighboring nodes of a node to the queue at each step.

The main difference between BFS and DFS is: BFS guarantees 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 once we introduce the framework.

This article will explain two typical BFS problems step-by-step: "Minimum Height of a Binary Tree" and "Minimum Steps to Unlock a Password Lock," teaching you how to write BFS algorithms.

1. Algorithm Framework

Let's start by discussing the common scenarios where BFS (Breadth-First Search) is used. Essentially, the problem is to find the shortest distance from a starting point start to an endpoint target in a "graph". While this might sound tedious, BFS problems are essentially about this. Once you understand this fundamental concept, you can confidently tackle various problem formulations.

This broad description can have many variations. For example, in a maze where some cells are walls and cannot be passed through, what is the shortest distance from the start to the end? What if the maze has "portals" that can instantly transport you?

Another example is transforming one word into another by replacing characters one at a time, requiring the minimum number of replacements.

Or consider the game of connecting tiles, where two tiles can be eliminated not just by matching patterns, but also by ensuring the shortest path connecting them has no more than two bends. How does the game determine the number of bends between two tiles when you click on them?

And so on...

Despite these fancy variations, the core problem remains the same: it's a "graph" where you need to find the shortest path from a start point to an endpoint. This is the essence of BFS. Once you understand this framework, you can easily apply it to different problems.

Just remember the following framework:

// 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 node

So, 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 depth

func 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;
}

Here, note the coordination between the while loop and the for loop. The while loop controls the levels as you go deeper, and the for loop uses the sz variable to traverse the nodes of each binary tree level from left to right:

This is important and a common pattern in standard BFS problems. However, in the Dijkstra Algorithm Template Framework, we modify this code pattern. After reading and understanding this article, you can explore how BFS evolves into the Dijkstra algorithm to find the shortest path in weighted graphs.

That being said, a binary tree is a simple data structure. I believe you can understand the above code. In fact, other complex problems are variations of this framework. Before delving into complex problems, let's address two questions:

1. Why can BFS find the shortest distance, but DFS cannot?

First, look at the logic of BFS. Every time depth increases, all nodes in the queue take a step forward, ensuring that the first time you reach the end, the number of steps taken is the minimum.

Can't DFS find the shortest path? Actually, it can, but the time complexity is much higher. Think about it, DFS relies on a recursive stack to record the path traveled. To find the shortest path, you would need to explore all branches of the binary tree to compare the lengths of paths, right? BFS, using a queue, can find the shortest distance without traversing the entire tree by advancing step by step simultaneously.

To put it simply, DFS is like a line, while BFS is like a surface; DFS is a solo effort, while BFS is collective 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 has high space complexity, whereas DFS has lower space complexity.

Let's use the example of solving a binary tree problem again. Suppose the binary tree is a full binary tree with N nodes. For the DFS algorithm, space complexity is mainly due to the recursive stack, which at worst is the height of the tree, i.e., $O(logN)$.

On the other hand, with the BFS algorithm, the queue stores all nodes on a level of the binary tree. Thus, in the worst case, the space complexity would be the number of nodes at the lowest level, or N/2, which in Big O notation is $O(N)$.

Therefore, BFS comes with a cost. Typically, BFS is used to find the shortest path, while DFS is used more often for other purposes (mainly because recursive code is easier to write).

Now that you know enough about BFS, let's tackle a more challenging problem to deepen your understanding of the framework.

3. Minimum Turns to Unlock a Safe

This is LeetCode problem 752, "Open the Lock," which is quite interesting:

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".

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.

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) -> int

func 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 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:

1. 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.

2. There is no termination condition. According to the problem, we should stop and return the number of moves once we find the target.

3. 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('');
}

At this point, we have solved the problem. There's a minor optimization: you don't need the dead hash set. You can directly initialize these elements into the visited set, which achieves the same effect and might be more elegant.

4. Bidirectional BFS Optimization

Do you think the BFS algorithm ends here? Quite the opposite. There's a slightly more advanced optimization technique: Bidirectional BFS, which can further enhance the efficiency of the algorithm.

Due to space limitations, here's a brief distinction: The traditional BFS framework spreads out from the starting point until it reaches the endpoint; whereas Bidirectional BFS spreads out from both the starting and ending points simultaneously, stopping when the two sides intersect.

Why does this improve efficiency? In terms of Big O notation analyzing algorithm complexity, both have the worst-case complexity of $O(N)$. However, in practice, Bidirectional BFS tends to be faster. I'll show you two diagrams that make this clear at a glance:

In the tree structure shown in the diagrams, if the endpoint is at the bottom, the traditional BFS strategy will search through all the nodes of the entire tree to finally find the target. In contrast, Bidirectional BFS only traverses half of the tree before the intersection occurs, which means the shortest distance is found. This example intuitively demonstrates that Bidirectional BFS is more efficient than traditional BFS.

However, Bidirectional BFS has limitations because you must know where the endpoint is. For instance, in the problem of finding the minimum height of a binary tree we just discussed, you don't know where the endpoint is initially, so Bidirectional BFS can't be used. But for the second problem of the password lock, Bidirectional BFS can be applied to enhance efficiency, with only slight code modifications required:

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
            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
            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
            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
        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.