Of course! LeetCode 752, "Open the Lock," is a classic problem that is perfectly solved using a Breadth-First Search (BFS) algorithm. It's a great problem for understanding graph traversal and shortest path unweighted graphs.

Here is a complete Python solution, followed by a detailed explanation of the approach, code, and complexity.

Problem Summary

You have a 4-wheel lock, each wheel displaying digits from 0 to 9. The lock starts at 0000. You are given a list of deadends, which are combinations that you cannot turn into. If you reach a deadend, you cannot proceed. You are also given a target combination, e.g., "0202". Each move consists of turning one wheel one slot. You can turn a wheel up (from 9 to 0) or down (from 0 to 9).

Goal: Find the minimum number of moves required to open the lock (reach the target). If it's impossible to reach the target, return -1.

Approach: Breadth-First Search (BFS)

This problem is essentially finding the shortest path in an unweighted graph. Here's why:

• Nodes: Each possible 4-digit combination (e.g., "0000", "0001", "1000") is a node.
• Edges: An edge exists between two nodes if you can get from one combination to the other in a single move (i.e., they differ by exactly one wheel, turned by one slot).

BFS is the ideal algorithm for finding the shortest path in an unweighted graph because it explores the graph layer by layer. All nodes at distance 1 are explored, then all nodes at distance 2, and so on. The moment we find the target, we know we've found the shortest path.

Algorithm Steps:

1. Handle Edge Cases:

   • If the starting combination "0000" is in the deadends list, it's impossible to start, so return -1.
   • If the target is "0000", we're already there, so return 0.

2. Initialize:

   
   （图片来源网络，侵删）
   • A queue for BFS. We'll store tuples of (current_combination, number_of_moves). Start by enqueuing ("0000", 0).
   • A visited set to keep track of combinations we've already seen to avoid cycles and redundant processing. Add "0000" to this set.

3. BFS Loop:

   • While the queue is not empty:
     • Dequeue the current combination and its move count.
     • If this combination is the target, return the move count.
     • If this combination is a deadend, skip it (don't explore its neighbors).
     • Otherwise, generate all 8 possible next combinations (4 wheels, 2 directions each).
     • For each new combination:
       • If it has not been visited and is not a deadend:
         • Add it to the visited set.
         • Enqueue the new combination with move_count + 1.

4. Conclusion:

   • If the BFS loop finishes without finding the target, it means the target is unreachable. Return -1.

Python Solution

from collections import deque
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        """
        Solves the Open the Lock problem using Breadth-First Search (BFS).
        """
        # Helper function to generate all possible next moves from a given combination
        def get_neighbors(combination):
            neighbors = []
            for i in range(4):
                digit = int(combination[i])
                # Turn the wheel up
                up_digit = (digit + 1) % 10
                neighbors.append(combination[:i] + str(up_digit) + combination[i+1:])
                # Turn the wheel down
                down_digit = (digit - 1) % 10
                neighbors.append(combination[:i] + str(down_digit) + combination[i+1:])
            return neighbors
        # Convert deadends to a set for O(1) average-time lookups
        deadends_set = set(deadends)
        # Edge Case 1: The starting point is a deadend
        if "0000" in deadends_set:
            return -1
        # Initialize the BFS queue with the starting combination and 0 moves
        # Use a deque for efficient appends and poplefts
        queue = deque([("0000", 0)])
        # Initialize a visited set to avoid cycles
        visited = set()
        visited.add("0000")
        # Perform BFS
        while queue:
            current_combination, moves = queue.popleft()
            # If we've reached the target, return the number of moves
            if current_combination == target:
                return moves
            # If the current combination is a deadend, skip it
            if current_combination in deadends_set:
                continue
            # Explore all neighbors
            for neighbor in get_neighbors(current_combination):
                # If we haven't visited this neighbor and it's not a deadend
                if neighbor not in visited and neighbor not in deadends_set:
                    visited.add(neighbor)
                    queue.append((neighbor, moves + 1))
        # If the queue is empty and we haven't found the target, it's impossible
        return -1

Explanation of the Code

1. get_neighbors(combination): This is a crucial helper function. For a given 4-digit string (e.g., "0000"), it iterates through each of the 4 positions. For each position, it calculates the new digit for turning the wheel up ((digit + 1) % 10) and down ((digit - 1) % 10). The modulo (% 10) elegantly handles the wrap-around from 9 to 0 and 0 to 9. It then constructs the new neighbor string and adds it to a list.

2. deadends_set = set(deadends): Converting the list of deadends to a set is a critical optimization. Checking if an item exists in a set (item in my_set) is, on average, an O(1) operation, whereas checking in a list (item in my_list) is an O(N) operation. This makes a huge difference for performance.

3. Edge Case Handling: The first check if "0000" in deadends_set handles the scenario where we can't even make the first move.

4. BFS Initialization: We use collections.deque for our queue. It's highly efficient for adding items to the end (append) and removing items from the front (popleft), which is the core of a BFS algorithm. We start the queue with our initial state ("0000", 0).

5. visited Set: This set is essential to prevent the algorithm from getting stuck in infinite loops. For example, from "0000", we can go to "1000", and from "1000", one of the neighbors is "0000". Without the visited set, we would go back and forth forever. We add a node to visited as soon as we enqueue it.

6. The while loop: This is the main engine of the BFS.

   • current_combination, moves = queue.popleft(): We get the next combination to explore and the number of moves it took to get there.
   • if current_combination == target: If we've found our goal, we immediately return the moves count. Because we are using BFS, this is guaranteed to be the shortest path.
   • if current_combination in deadends_set: If we stumble upon a deadend, we simply stop processing this path.
   • The for loop generates all valid, unvisited neighbors and adds them to the queue for future exploration, incrementing the move count.

7. return -1: If the while loop completes, it means we have explored every reachable combination from "0000" without finding the target. Therefore, the target is unreachable, and we return -1.

Complexity Analysis

• *Time Complexity: O(10^4 8) = O(1)**

  • In the worst case, we might have to visit every possible combination on the lock. There are 10,000 possible combinations (from "0000" to "9999").
  • For each combination, we generate 8 neighbors.
  • So, the time complexity is proportional to the number of nodes (10,000) times the work per node (generating 8 neighbors and checking sets, which are O(1) operations).
  • Since the number of combinations is fixed (10,000), the time complexity is effectively constant, O(1), for the problem's constraints.

• Space Complexity: O(10^4) = O(1)

  • The visited set and the queue can, in the worst case, store all 10,000 combinations.
  • Therefore, the space complexity is also proportional to the total number of combinations, which is O(1) for this problem.