BFS Algorithm Common Patterns and Code Template

I have emphasized multiple times that algorithms like DFS, backtracking, and BFS essentially abstract a specific problem into a tree structure and then traverse this tree to conduct brute-force enumeration. Thus, the code for these enumeration algorithms is fundamentally tree traversal code.

To clarify the causal relationships here:

The essence of DFS/backtracking algorithms is to recursively traverse an enumeration tree (multi-way tree), which is derived from the recursive traversal of binary trees. Therefore, I say that the essence of DFS/backtracking algorithms is the recursive traversal of binary trees.

The essence of BFS algorithms is to traverse a graph. As you will see, the framework for BFS algorithms is the code for traversing graph nodes in DFS/BFS Traversal of Graph Structures.

In fact, graph traversal algorithms are essentially multi-way tree traversal algorithms with an added visited array to prevent infinite loops; multi-way tree traversal algorithms are derived from binary tree traversal algorithms. Therefore, I say the essence of BFS algorithms is level-order traversal of binary trees.

Why is the BFS algorithm often used to solve shortest path problems? I explained this in detail using the example of finding the minimum depth of a binary tree in Recursive/Level Order Traversal of Binary Trees.

In essence, what we call the shortest path can be likened to problems of finding the minimum depth of a binary tree (finding the leaf node closest to the root). Recursive traversal requires visiting all nodes of the tree to find the target node, whereas level-order traversal can achieve this without visiting all nodes, making it suitable for solving shortest path problems.

Is this explanation clear enough?

So, before reading this article, make sure you have learned Recursive/Level Order Traversal of Binary Trees, Recursive/Level Order Traversal of Multi-way Trees, and DFS/BFS Traversal of Graph Structures. Understanding these basic data structure traversal algorithms is crucial as it makes other algorithms easier to grasp.

The focus of this article is to teach you how to abstract and transform specific algorithm problems, then apply the BFS algorithm framework to solve them.

In real interview questions, you are generally not asked to directly traverse standard data structures like trees/graphs. Instead, you are given a specific scenario and need to abstract it into a standard graph/tree structure, then use the BFS algorithm to enumerate the solution.

For example, in a maze game, you are asked to calculate the minimum number of steps to reach the exit. If the maze includes teleportation portals that instantly transport you to another location, what is the minimum number of steps then?

Or, given two words, you are required to transform one into the other through a series of replacements, deletions, or insertions of characters. How many operations are needed at minimum?

Another example is a matching game where two blocks can be eliminated only if they have the same pattern and the shortest connecting line between them has no more than two turns. When you play such a game and click on two coordinates, how does the game determine the number of turns in the shortest connecting line?

These examples may initially seem unrelated to tree/graph structures, but with a bit of abstraction, they are indeed traversals of tree/graph structures. It becomes straightforward and monotonous.

Let's use a few examples to illustrate the BFS framework, and you will find these types of problems become much easier to solve.

1. Algorithm Framework

The framework for BFS (Breadth-First Search) is essentially the same as the BFS traversal of graph structures provided in Graph Traversal, and there are three ways to write it.

For practical BFS algorithm problems, the first method is the simplest but has significant limitations and is rarely used. The second method is the most commonly used, as it can solve most medium-level BFS algorithm problems. The third method is slightly more complex but offers the highest flexibility and may be used in more challenging BFS problems. In the next chapter, BFS Algorithm Exercises, there will be some more difficult problems employing the third method, which you can try on your own.

The examples in this article are of medium difficulty, so the solutions provided here will follow the second method:

// BFS traversal of the graph starting from s, and record the steps
// When the target node is reached, return the number of steps
int bfs(int s, int target) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> q = new LinkedList<>();
    q.offer(s);
    visited[s] = true;
    // record the number of steps taken from s to the current node
    int step = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int cur = q.poll();
            System.out.println("visit " + cur + " at step " + step);
            // determine if the target point is reached
            if (cur == target) {
                return step;
            }
            // add the neighbors to the queue to search around
            for (int to : neighborsOf(cur)) {
                if (!visited[to]) {
                    q.offer(to);
                    visited[to] = true;
                }
            }
        }
        step++;
    }
    // If we reach here, it means the target node was not found in the graph
    return -1;
}

// BFS traversal of the graph starting from s, and record the steps
// When the target node is reached, return the number of steps
int bfs(const Graph& graph, int s, int target) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    // record the number of steps taken from s to the current node taken
    int step = 0;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int cur = q.front();
            q.pop();
            cout << "visit " << cur << " at step " << step << endl;
            // determine if the target point is reached
            if (cur == target) {
                return step;
            }
            // add the neighbors to the queue to search around
            for (int to : neighborsOf(cur)) {
                if (!visited[to]) {
                    q.push(to);
                    visited[to] = true;
                }
            }
        }
        step++;
    }
    // If we reach here, it means the target node was not found in the graph
    return -1;
}

# BFS traversal of the graph starting from s, and record the steps
def bfs(graph, s):
    visited = [False] * len(graph)
    q = deque([s])
    visited[s] = True
    # record the number of steps taken from s to the current node
    step = 0
    
    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            print(f"visit {cur} at step {step}")
            # determine if the target point is reached
            if cur == target:
                return step

            # add neighboring nodes to the queue, and spread the search outward
            for to in neighborsOf(cur):
                if not visited[to]:
                    q.append(to)
                    visited[to] = True
        step += 1
    # If we reach here, it means the target node was not found in the graph
    return -1

// BFS traversal of the graph starting from s, and record the steps
// When the target node is reached, return the number of steps
func bfs(graph Graph, s int, target int) int {
    visited := make([]bool, graph.size())
    q := []int{s}
    visited[s] = true
    // record the number of steps taken from s to the current node in the traversal
    step := 0
    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            fmt.Printf("visit %d at step %d\n", cur, step)
            // determine if the target point is reached
            if cur == target {
                return step
            }

            // add the neighbors to the queue to search around
            for _, to := range neighborsOf(cur) {
                if !visited[to] {
                    q = append(q, to)
                    visited[to] = true
                }
            }
        }
        step++
    }
    // If we reach here, it means the target node was not found in the graph
    return -1
}

// BFS traversal of the graph starting from s, and record the steps
// When the target node is reached, return the number of steps
var bfs = function(graph, s, target) {
    var visited = new Array(graph.size()).fill(false);
    var q = [];
    q.push(s);
    visited[s] = true;
    // record the number of steps taken from s to the current node in the traversal
    var step = 0;

    while (q.length !== 0) {
        var sz = q.length;
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();
            // visit the current node
            console.log("visit " + cur + " at step " + step);
            // determine if the target point is reached
            if (cur === target) {
                return step;
            }
            // add the neighbors to the queue to search around
            var neighbors = neighborsOf(cur);
            for (var i = 0; i < neighbors.length; i++) {
                var to = neighbors[i];
                if (!visited[to]) {
                    q.push(to);
                    visited[to] = true;
                }
            }
        }
        step++;
    }
    // If we reach here, it means the target node was not found in the graph
    return -1;
}

The above code framework is almost copied from DFS/BFS Traversal of Graph Structures, with the addition of a target parameter. The algorithm terminates and returns the number of steps once it first reaches the target.

Let's look at a few specific examples of how to apply this framework.

2. Problem 773: Sliding Puzzle

LeetCode Problem 773 "Sliding Puzzle" is a problem that can be solved using the BFS framework. The problem is described as follows:

You are given a 2x3 sliding puzzle represented by a 2x3 array board. The puzzle contains numbers 0 to 5, where number 0 represents the empty space. You can move the numbers, and when board becomes [[1,2,3],[4,5,0]], you win the game.

Write an algorithm to calculate the minimum number of moves needed to win the game. If the game cannot be won, return -1.

For example, given the array board = [[4,1,2],[5,0,3]], the algorithm should return 5:

If the input is board = [[1,2,3],[5,4,0]], the algorithm returns -1 because it is impossible to win the game from this configuration.

This problem is quite interesting; it reminds me of similar puzzle games from childhood, like the Huarong Road:

You need to move these blocks and find a way to move Cao Cao from the starting position to the exit at the bottom.

The Huarong Road is probably more difficult because, in this LeetCode problem, each block is the same size, whereas in the Huarong Road, each block can be a different size.

Returning to this problem, how can we abstract it into a tree/graph structure so that we can solve it using the BFS algorithm framework?

In fact, the initial state of the board can be considered as the starting point:

[[2,4,1],
 [5,0,3]]

Our ultimate goal is to transform the chessboard into this state:

[[1,2,3],
 [4,5,0]]

This can be considered as the endpoint.

Now, doesn't this problem become a graph problem? Essentially, the question is asking for the shortest path from the start to the endpoint.

Who are the neighboring nodes of the starting point? By swapping the number 0 with the numbers above, below, left, and right, you actually get the four neighboring nodes of the start point (since the board size in this problem is 2x3, the actual neighboring nodes within the index boundaries will be less than four):

By analogy, each of these four neighboring nodes also has its own four neighboring nodes, forming a graph structure.

Starting from the initial point, I use the BFS algorithm to traverse this graph. The number of steps taken to reach the endpoint for the first time is the answer.

The pseudocode is as follows:

int bfs(int[][] board, int[][] target) {
    Queue<int[][]> q = new LinkedList<>();
    HashSet visited = new HashSet<>();

    // add the start point to the queue
    q.offer(board);
    visited.add(board);

    int step = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int[][] cur = q.poll();
            // determine if the end point is reached
            if (cur == target) {
                return step;
            }
            // add the neighbors of the current node to the queue
            for (int[][] neighbor : getNeighbors(cur)) {
                if (!visited.contains(neighbor)) {
                    q.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        step++;
    }
    return -1;
}

List<int[][]> getNeighbors(int[][] board) {
    // swap the number 0 with the numbers above, below, left, and right, to get 4 neighbors
}

For this problem, the abstracted graph structure may contain cycles, so we need a visited array to record nodes that have already been traversed to avoid infinite loops caused by cycles.

For example, if I start from the node [[2,4,1],[5,0,3]], moving the number 0 to the right results in a new node [[2,4,1],[5,3,0]]. However, in this new node, 0 can also move back to the left, returning to [[2,4,1],[5,0,3]], which creates a cycle. Thus, we need a visited hash set to record nodes that have been visited, preventing infinite loops due to cycles.

Another issue is that in this problem, the board is a two-dimensional array. As discussed in Hash Table/Hash Set Basics, mutable data structures like two-dimensional arrays cannot be directly added to a hash set.

Therefore, we need to use some techniques to transform the two-dimensional array into an immutable type before storing it in a hash set. A common solution is to serialize the two-dimensional array into a string, which can then be stored in the hash set.

The tricky part is that the two-dimensional array has concepts of "up, down, left, and right," so how do we exchange the number 0 with adjacent numbers once compressed into a one-dimensional string?

For this problem, since the input array size is always 2 x 3, we can manually write out this mapping:

// Record the adjacent indices of one-dimensional strings
int[][] neighbor = new int[][]{
    {1, 3},
    {0, 4, 2},
    {1, 5},
    {0, 4},
    {3, 1, 5},
    {4, 2}
};

// Record the adjacent indices of one-dimensional strings
int neighbor[6][3] = {
    {1, 3},
    {0, 4, 2},
    {1, 5},
    {0, 4},
    {3, 1, 5},
    {4, 2}
};

# Record the adjacent indices of a one-dimensional string
neighbor = [
    [1, 3],
    [0, 4, 2],
    [1, 5],
    [0, 4],
    [3, 1, 5],
    [4, 2]
]

// Record adjacent indices of one-dimensional strings
neighbor := [][]int{
    {1, 3},
    {0, 4, 2},
    {1, 5},
    {0, 4},
    {3, 1, 5},
    {4, 2},
}

// Record the adjacent indices of one-dimensional strings
var neighbor = [
    [1, 3],
    [0, 4, 2],
    [1, 5],
    [0, 4],
    [3, 1, 5],
    [4, 2]
];

The meaning of this mapping is that in a one-dimensional string, the index i has adjacent indices in the two-dimensional array as neighbor[i]:

int[][] generateNeighborMapping(int m, int n) {
    int[][] neighbor = new int[m * n][];
    for (int i = 0; i < m * n; i++) {
        List<Integer> neighbors = new ArrayList<>();

        // if it is not the first column, it has a left neighbor
        if (i % n != 0) neighbors.add(i - 1);
        
        // if it is not the last column, it has a right neighbor
        if (i % n != n - 1) neighbors.add(i + 1);
        
        // if it is not the first row, it has an upper neighbor
        if (i - n >= 0) neighbors.add(i - n);
        
        // if it is not the last row, it has a lower neighbor
        if (i + n < m * n) neighbors.add(i + n);

        // Java language feature, convert List type to int[] array
        neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
    }
    return neighbor;
}

vector<vector<int>> generateNeighborMapping(int m, int n) {
    vector<vector<int>> neighbor(m * n);
    for (int i = 0; i < m * n; i++) {
        vector<int> neighbors;

        // if it's not the first column, it has a left neighbor
        if (i % n != 0) neighbors.push_back(i - 1);
        // if it's not the last column, it has a right neighbor
        if (i % n != n - 1) neighbors.push_back(i + 1);
        // if it's not the first row, it has an upper neighbor
        if (i - n >= 0) neighbors.push_back(i - n);
        // if it's not the last row, it has a lower neighbor
        if (i + n < m * n) neighbors.push_back(i + n);

        neighbor[i] = neighbors;
    }
    return neighbor;
}

def generateNeighborMapping(m: int, n: int) -> List[List[int]]:
    neighbor = [[] for _ in range(m * n)]
    for i in range(m * n):
        neighbors = []

        # if not the first column, it has a left neighbor
        if i % n != 0: neighbors.append(i - 1)
        
        # if not the last column, it has a right neighbor
        if i % n != n - 1: neighbors.append(i + 1)
        
        # if not the first row, it has an upper neighbor
        if i - n >= 0: neighbors.append(i - n)
        
        # if not the last row, it has a lower neighbor
        if i + n < m * n: neighbors.append(i + n)

        neighbor[i] = neighbors
    return neighbor

func generateNeighborMapping(m, n int) [][]int {
    neighbor := make([][]int, m*n)
    for i := 0; i < m*n; i++ {
        neighbors := make([]int, 0)

        // if it's not the first column, it has a left neighbor
        if i % n != 0 {
            neighbors = append(neighbors, i-1)
        }
        // if it's not the last column, it has a right neighbor
        if i % n != n-1 {
            neighbors = append(neighbors, i+1)
        }
        // if it's not the first row, it has an upper neighbor
        if i-n >= 0 {
            neighbors = append(neighbors, i-n)
        }
        // if it's not the last row, it has a lower neighbor
        if i+n < m*n {
            neighbors = append(neighbors, i+n)
        }

        neighbor[i] = neighbors
    }
    return neighbor
}

function generateNeighborMapping(m, n) {
    const neighbor = new Array(m * n).fill(0).map(() => []);
    for (let i = 0; i < m * n; i++) {
        const neighbors = [];

        // if not in the first column, has a left neighbor
        if (i % n !== 0) neighbors.push(i - 1);
        
        // if not in the last column, has a right neighbor
        if (i % n !== n - 1) neighbors.push(i + 1);
        
        // if not in the first row, has an upper neighbor
        if (i - n >= 0) neighbors.push(i - n);
        
        // if not in the last row, has a lower neighbor
        if (i + n < m * n) neighbors.push(i + n);

        neighbor[i] = neighbors;
    }
    return neighbor;
}

In this way, regardless of where the number 0 is located, you can use this index mapping to obtain its adjacent index for swapping. Below is the complete code implementation:

class Solution {
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        // convert the 2x3 array to a string as the starting point of BFS
        String start = "";
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                start = start + board[i][j];
            }
        }

        // ***** BFS algorithm framework starts *****
        Queue<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        // start BFS search from the starting point
        q.offer(start);
        visited.add(start);

        int step = 0;
        while (!q.isEmpty()) {

            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                // determine if the target state is reached
                if (target.equals(cur)) {
                    return step;
                }
                // swap number 0 with its adjacent numbers
                for (String neighborBoard : getNeighbors(cur)) {
                    // prevent from going back
                    if (!visited.contains(neighborBoard)) {
                        q.offer(neighborBoard);
                        visited.add(neighborBoard);
                    }
                }
            }
            step++;
        }
        // ***** BFS algorithm framework ends *****
        return -1;
    }

    private List<String> getNeighbors(String board) {
        // record the adjacent indices of the one-dimensional string
        int[][] mapping = new int[][]{

                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        int idx = board.indexOf('0');
        List<String> neighbors = new ArrayList<>();
        for (int adj : mapping[idx]) {
            String new_board = swap(board.toCharArray(), adj, idx);
            neighbors.add(new_board);
        }
        return neighbors;
    }

    private String swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }
}

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string target = "123450";
        // convert the 2x3 array to a string as the starting point of BFS
        string start = "";
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                start = start + to_string(board[i][j]);
            }
        }

        // ***** BFS algorithm framework starts *****
        queue<string> q;
        unordered_set<string> visited;
        // start BFS search from the starting point
        q.push(start);
        visited.insert(start);

        int step = 0;
        while (!q.empty()) {

            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                string cur = q.front();
                q.pop();
                // determine if the target state is reached
                if (target == cur) {
                    return step;
                }
                // swap number 0 with its adjacent numbers
                for (string neighborBoard : getNeighbors(cur)) {
                    // prevent from going back
                    if (!visited.count(neighborBoard)) {
                        q.push(neighborBoard);
                        visited.insert(neighborBoard);
                    }
                }
            }
            step++;
        }
        // ***** BFS algorithm framework ends *****
        return -1;
    }

    vector<string> getNeighbors(string board) {
        // record the adjacent indices of the one-dimensional string
        vector<vector<int>> mapping = {

            {1, 3},
            {0, 4, 2},
            {1, 5},
            {0, 4},
            {3, 1, 5},
            {4, 2}
        };

        int idx = board.find('0');
        vector<string> neighbors;
        for (int adj : mapping[idx]) {
            string new_board = swap(board, idx, adj);
            neighbors.push_back(new_board);
        }
        return neighbors;
    }

    string swap(string board, int i, int j) {
        char temp = board[i];
        board[i] = board[j];
        board[j] = temp;
        return board;
    }
};

from collections import deque

class Solution:
    def slidingPuzzle(self, board):
        target = "123450"
        # convert the 2x3 array to a string as the starting point of BFS
        start = ""
        for i in range(len(board)):
            for j in range(len(board[0])):
                start += str(board[i][j])
        
        # ***** BFS algorithm framework starts *****
        q = deque()
        visited = set()
        # start BFS search from the starting point
        q.append(start)
        visited.add(start)
        
        step = 0
        while q: 

            # number of nodes in the current layer
            sz = len(q)
            for _ in range(sz):
                cur = q.popleft()
                # determine if the target state is reached
                if cur == target:
                    return step
                # swap number 0 with its adjacent numbers
                for neighbor_board in self.getNeighbors(cur):
                    # prevent from going back
                    if neighbor_board not in visited:
                        q.append(neighbor_board)
                        visited.add(neighbor_board)
            step += 1
        # ***** BFS algorithm framework ends *****
        return -1

    def getNeighbors(self, board):
        # record the adjacent indices of the one-dimensional string
        mapping = [
            [1, 3],
            [0, 4, 2],
            [1, 5],
            [0, 4],
            [3, 1, 5],
            [4, 2]
        ] 

        
        idx = board.index('0')
        neighbors = []
        for adj in mapping[idx]:
            new_board = self.swap(board, idx, adj)
            neighbors.append(new_board)
        return neighbors

    def swap(self, board, i, j):
        chars = list(board)
        chars[i], chars[j] = chars[j], chars[i]
        return ''.join(chars)

func slidingPuzzle(board [][]int) int {
    target := "123450"
    // convert the 2x3 array to a string as the starting point of BFS
    start := ""
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            start += string(rune(board[i][j] + '0'))
        }
    }

    // ***** BFS algorithm framework starts *****
    queue := []string{start}
    visited := make(map[string]bool)
    visited[start] = true

    step := 0
    for len(queue) > 0 {

        sz := len(queue)
        for i := 0; i < sz; i++ {
            cur := queue[0]
            queue = queue[1:]
            // determine if the target state is reached
            if cur == target {
                return step
            }
            // swap number 0 with its adjacent numbers
            for _, neighbor := range getNeighbors(cur) {
                // prevent from going back
                if !visited[neighbor] {
                    queue = append(queue, neighbor)
                    visited[neighbor] = true
                }
            }
        }
        step++
    }
    // ***** BFS algorithm framework ends *****
    return -1
}

func getNeighbors(board string) []string {
    // record the adjacent indices of the one-dimensional string
    mapping := [][]int{

        {1, 3},
        {0, 4, 2},
        {1, 5},
        {0, 4},
        {3, 1, 5},
        {4, 2},
    }

    idx := strings.Index(board, "0")
    neighbors := []string{}
    for _, adj := range mapping[idx] {
        newBoard := swap(board, idx, adj)
        neighbors = append(neighbors, newBoard)
    }
    return neighbors
}

func swap(board string, i, j int) string {
    chars := []rune(board)
    chars[i], chars[j] = chars[j], chars[i]
    return string(chars)
}

var slidingPuzzle = function(board) {
    const target = "123450";
    // convert the 2x3 array to a string as the starting point of BFS
    let start = "";
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            start += board[i][j];
        }
    }

    // ***** BFS algorithm framework starts *****
    const queue = [start];
    const visited = new Set();
    visited.add(start);

    let step = 0;
    while (queue.length > 0) {

        const sz = queue.length;
        for (let i = 0; i < sz; i++) {
            const cur = queue.shift();
            // determine if the target state is reached
            if (cur === target) {
                return step;
            }
            // swap number 0 with its adjacent numbers
            for (const neighbor of getNeighbors(cur)) {
                // prevent from going back
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        step++;
    }
    // ***** BFS algorithm framework ends *****
    return -1;
};

function getNeighbors(board) {
    // record the adjacent indices of the one-dimensional string
    const mapping = [

        [1, 3],
        [0, 4, 2],
        [1, 5],
        [0, 4],
        [3, 1, 5],
        [4, 2],
    ];

    const idx = board.indexOf('0');
    const neighbors = [];
    for (const adj of mapping[idx]) {
        const newBoard = swap(board, idx, adj);
        neighbors.push(newBoard);
    }
    return neighbors;
}

function swap(board, i, j) {
    const chars = board.split('');
    [chars[i], chars[j]] = [chars[j], chars[i]];
    return chars.join('');
}

This problem is solved. You will find that the BFS algorithm follows a fixed pattern. The challenge lies in converting the problem into a BFS brute-force model, then using a reasonable method to convert multi-dimensional arrays into strings for the hash set to record visited nodes.

Let's look at another real-world problem.

3. Minimum Turns to Unlock a Password Lock

Consider 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 described is similar to the common password lock we see in daily life. If there are no constraints, calculating the minimum number of moves is straightforward. For example, if you want to reach "1234", you can simply move each digit: the minimum number of moves is 1 + 2 + 3 + 4 = 10.

However, the challenge arises when you cannot encounter deadends during the process of turning the lock. How would you handle deadends to ensure the total number of moves is minimized?

Do not get bogged down in details or try to consider all specific scenarios. Remember, the essence of an algorithm is brute-force. By starting directly from "0000" and exhaustively trying all possible combinations, can we really fail to find the minimum number of moves?

Step one, disregard all constraints, including deadends and target. Consider this question: If you were to design an algorithm to enumerate all possible password combinations, how would you do it?

Starting from "0000", if you turn the lock once, how many possibilities are there? There are 4 positions, each can be turned up or down, leading to possibilities like "1000", "9000", "0100", "0900"... totaling 8 potential combinations.

Then, using these 8 combinations as a base, each can be turned once more to generate 8 new combinations, and so on...

Can you visualize the recursive tree in your mind? It should be an octal tree, with each node having 8 child nodes, branching downwards.

The following pseudocode describes this idea, using a level-order traversal of an octal tree:

// 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 find the minimum number of moves
void BFS(String target) {
    Queue<String> q = new LinkedList<>();
    q.offer("0000");

    int step = 0;

    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
            if (cur.equals(target)) {
                return step;
            }

            // a password can derive 8 neighboring passwords
            for (String neighbor : getNeighbors(cur)) {
                q.offer(neighbor);
            }
        }
        // increase the step count here
        step++;
    }
}
// increment or decrement each digit of s by one, return 8 neighboring passwords
List<String> getNeighbors(String s) {
    List<String> neighbors = new ArrayList<>();
    for (int i = 0; i < 4; i++) {
        neighbors.add(plusOne(s, i));
        neighbors.add(minusOne(s, i));
    }
    return neighbors;
}

// 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 find the minimum number of moves
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 the end point is reached
            if (cur == target) {
                return step;
            }
            // a password can derive 8 neighboring passwords
            for (string neighbor : getNeighbors(cur)) {
                q.push(neighbor);
            }
        }
        // increment the step count here
        step++;
    }
    return -1;
}

// increment or decrement each digit of s by one, return 8 neighboring passwords
vector<string> getNeighbors(string s) {
    vector<string> neighbors;
    for (int i = 0; i < 4; i++) {
        neighbors.push_back(plusOne(s, i));
        neighbors.push_back(minusOne(s, i));
    }
    return neighbors;
}

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 find the minimum number of moves
def BFS(target: str) -> int:
    q = ['0000']
    
    while q:
        sz = len(q)
        # spread all nodes in the current queue to their surroundings
        for _ in range(sz):
            cur = q.pop(0)
            # determine if the end point is reached
            if cur == target:
                return step
            # add the neighbors of a node to the queue
            for neighbor in getNeighbors(cur):
                q.append(neighbor)
        # increment the step count here
        step += 1
    return -1

# increment or decrement each digit of s by one, return 8 neighboring passwords
def getNeighbors(s: str) -> List[str]:
    neighbors = []
    for i in range(4):
        neighbors.append(plusOne(s, i))
        neighbors.append(minusOne(s, i))
    return neighbors

// 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 to find the minimum number of moves
func BFS(target string) int {
    q := []string{"0000"}
    step := 0

    for len(q) > 0 {
        sz := len(q)
        // spread all nodes in the current queue to their surroundings
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            // determine if the end point is reached
            if cur == target {
                return step
            }
            // add the neighbors of a node to the queue
            for _, neighbor := range getNeighbors(cur) {
                q = append(q, neighbor)
            }
        }
        // increment the step count here
        step++
    }
    return -1
}

// increment or decrement each digit of s by one, return 8 neighboring passwords
func getNeighbors(s string) []string {
    neighbors := []string{}
    for i := 0; i < 4; i++ {
        neighbors = append(neighbors, plusOne(s, i))
        neighbors = append(neighbors, minusOne(s, i))
    }
    return neighbors
}

// 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 find the minimum number of moves
var BFS = function(target) {
    let q = ['0000'];

    let step = 0;

    while(q.length > 0) {
        let sz = q.length;
        // spread all nodes in the current queue to their surroundings
        for(let i = 0; i < sz; i++) {
            let cur = q.shift();
            // determine if the end point is reached
            if(cur == target) {
                return step;
            }

            // add the neighbors of a node to the queue
            for(let neighbor of getNeighbors(cur)) {
                q.push(neighbor);
            }
        }
        // increment the step count here
        step++;
    }

    return -1;
}

// increment or decrement each digit of s by one, return 8 neighboring passwords
function getNeighbors(s) {
    let neighbors = [];
    for(let i = 0; i < 4; i++) {
        neighbors.push(plusOne(s, i));
        neighbors.push(minusOne(s, i));
    }
    return neighbors;
}

This code can already enumerate all possible password combinations, but there are still some issues to address.

1. It retraces steps. We can turn the dial from "0000" to "1000", but when "1000" is dequeued, it can turn back to "0000", creating an infinite loop.

This problem is easy to solve. Essentially, it's about forming a loop. We can use a visited set to record passwords that have already been enumerated. If a password is encountered again, it should not be added back to the queue.

2. The deadends are not handled. Ideally, these "deadlock passwords" should not appear.

This issue is also easy to handle. Use an additional deadends set to record these deadlock passwords, and whenever one is encountered, do not add it to the queue.

Alternatively, it can be even simpler by initializing the visited set with the passwords from deadends. This also achieves the desired outcome.

Below is the complete code implementation:

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);
        if (deads.contains("0000")) return -1;

        // 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 (cur.equals(target))
                    return step;
                
                // add the valid adjacent nodes of a node to the queue
                for (String neighbor : getNeighbors(cur)) {
                    if (!visited.contains(neighbor) && !deads.contains(neighbor)) {
                        q.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            // 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);
    }

    // increment or decrement each digit of s by one, return 8 neighboring passwords
    List<String> getNeighbors(String s) {
        List<String> neighbors = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            neighbors.add(plusOne(s, i));
            neighbors.add(minusOne(s, i));
        }
        return neighbors;
    }
}

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());
        if (deads.count("0000")) return -1;

        // 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 is reached
                if (cur == target)
                    return step;
                
                // add the valid adjacent nodes of a node to the queue
                for (string neighbor : getNeighbors(cur)) {
                    if (!visited.count(neighbor) && !deads.count(neighbor)) {
                        q.push(neighbor);
                        visited.insert(neighbor);
                    }
                }
            }
            // 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) {
        if (s[j] == '9')
            s[j] = '0';
        else
            s[j] += 1;
        return s;
    }

    // turn s[i] down once
    string minusOne(string s, int j) {
        if (s[j] == '0')
            s[j] = '9';
        else
            s[j] -= 1;
        return s;
    }

    // increment or decrement each digit of s by one, return 8 neighboring passwords
    vector<string> getNeighbors(string s) {
        vector<string> neighbors;
        for (int i = 0; i < 4; i++) {
            neighbors.push_back(plusOne(s, i));
            neighbors.push_back(minusOne(s, i));
        }
        return neighbors;
    }
};

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        # record the deadends that need to be skipped
        deads = set(deadends)
        if "0000" in deads:
            return -1

        # 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 surroundings
            for _ in range(sz):
                cur = q.popleft()
                
                # determine if the end is reached
                if cur == target:
                    return step
                
                # add the valid adjacent nodes of a node to the queue
                for neighbor in self.getNeighbors(cur):
                    if neighbor not in visited and neighbor not in deads:
                        q.append(neighbor)
                        visited.add(neighbor)
            
            # increment the step count here
            step += 1
        
        # if the target password is not found after exhaustion, then 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] = chr(ord(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] = chr(ord(ch[j]) - 1)
        return ''.join(ch)

    # increment or decrement each digit of s by one, return 8 neighboring passwords
    def getNeighbors(self, s: str) -> List[str]:
        neighbors = []
        for i in range(4):
            neighbors.append(self.plusOne(s, i))
            neighbors.append(self.minusOne(s, i))
        return neighbors

func openLock(deadends []string, target string) int {
    // record the deadends that need to be skipped
    deads := make(map[string]struct{})
    for _, s := range deadends {
        deads[s] = struct{}{}
    }
    if _, found := deads["0000"]; found {
        return -1
    }

    // record the passwords that have been exhausted to prevent backtracking
    visited := make(map[string]struct{})
    q := make([]string, 0)
    // start breadth-first search from the starting point
    step := 0
    q = append(q, "0000")
    visited["0000"] = struct{}{}
    
    for len(q) > 0 {
        sz := len(q)
        // spread all nodes in the current queue to their surroundings
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            
            // determine if the end is reached
            if cur == target {
                return step
            }
            
            // add the valid adjacent nodes of a node to the queue
            for _, neighbor := range getNeighbors(cur) {
                if _, found := visited[neighbor]; !found {
                    if _, dead := deads[neighbor]; !dead {
                        q = append(q, neighbor)
                        visited[neighbor] = struct{}{}
                    }
                }
            }
        }
        // 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
func plusOne(s string, j int) string {
    ch := []rune(s)
    if ch[j] == '9' {
        ch[j] = '0'
    } else {
        ch[j]++
    }
    return string(ch)
}

// turn s[i] down once
func minusOne(s string, j int) string {
    ch := []rune(s)
    if ch[j] == '0' {
        ch[j] = '9'
    } else {
        ch[j]--
    }
    return string(ch)
}

// increment or decrement each digit of s by one, return 8 neighboring passwords
func getNeighbors(s string) []string {
    neighbors := make([]string, 0)
    for i := 0; i < 4; i++ {
        neighbors = append(neighbors, plusOne(s, i))
        neighbors = append(neighbors, minusOne(s, i))
    }
    return neighbors
}

var openLock = function(deadends, target) {
    // record the deadends that need to be skipped
    let deads = new Set(deadends);
    if (deads.has("0000")) return -1;

    // 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 surroundings
        for (let i = 0; i < sz; i++) {
            let cur = q.shift();
            
            // determine if the end is reached
            if (cur === target)
                return step;
            
            // add the valid adjacent nodes of a node to the queue
            for (let neighbor of getNeighbors(cur)) {
                if (!visited.has(neighbor) && !deads.has(neighbor)) {
                    q.push(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        // 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
var plusOne = function(s, j) {
    let ch = s.split('');
    if (ch[j] === '9')
        ch[j] = '0';
    else
        ch[j] = (parseInt(ch[j]) + 1).toString();
    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] = (parseInt(ch[j]) - 1).toString();
    return ch.join('');
};

// increment or decrement each digit of s by one, return 8 neighboring passwords
var getNeighbors = function(s) {
    let neighbors = [];
    for (let i = 0; i < 4; i++) {
        neighbors.push(plusOne(s, i));
        neighbors.push(minusOne(s, i));
    }
    return neighbors;
};