Problem statement

https://leetcode.com/problems/open-the-lock/

Solution 1: Usual bfs

We can look at this problem as graph problem, where we need to find shortest way between given two nodes. We can do classical bfs to do it.

Complexity

The worst time complexity is O(E), where E is number of edges and it can be 10000 * 8/2, because we have 10000 nodes and each node is connected with 8 others. Space complexity O(N), where N is size of deadends.

Code

class Solution:
    def openLock(self, deadends, target):
        
        dead = set(deadends)
        queue = deque([(0, "0000")])
        
        if "0000" in dead: return -1
        
        while queue:
            steps, code = queue.popleft()
            if code == target: return steps
            
            for i in range(4):
                d = int(code[i])
                for k in (d-1)%10, (d+1)%10:
                    cand = code[:i] + str(k) + code[i+1:]
                    if cand not in dead: 
                        dead.add(cand)
                        queue.append((steps+1, cand))

        return -1

Solution 2: Bidirectional bfs

There is also bidirectional bfs, which has the same worst time complexity, but which in average will work several times faster. The idea is to start from both ends and each time choose the end with smaller size of queue. Here we need to be careful: Our invariant, that at each moment of time in our queues we have number of steps (first elements):

[i,i,..., i, i+1, i+1, ..., i+1] and [j,j,..., j, j+1, j+1, ..., j+1]

We extract left element from first queue and we need to check if it is in second. At this moment we for sure know that distance is not more than i + j. However, it can be either i+j or i+j+1, and we need to check all elements with length i to mare sure there is no element from second queue with steps j. So, first time we see that sum of first elements from our queue is more than limit, it means that we finished to process all candidates, so we can return answer.

Remark

In this specific problem, because of bipartite structure of our graph, bidirectional bfs can be optimized: for given i it can happen than only j or j+1 is in visited set, but not both of them, so 2 lines when we check limit can be removed. However in this case alrorithm become less universal, so I prefer it as it is, so you can reuse this pattern in other problems. Actually I already used it in some other problem, but I do not remember what exacty, please let me know if you have any idea.

Complexity

Is the same as previous approach, but in practice it works much faster.

Code

class Solution:
    def openLock(self, deadends, target):
        dead = set(deadends)
        if "0000" in dead: return -1
        
        queue1 = deque([(0, "0000")])
        queue2 = deque([(0, target)])
        visited1 = {"0000": 0}
        visited2 = {target: 0}
        
        limit, ans = float("inf"), float("inf")

        while queue1:
            if len(queue1) > len(queue2):
                queue1, queue2 = queue2, queue1
                visited1, visited2 = visited2, visited1
                
            steps, code = queue1.popleft()
            if steps + queue2[0][0] > limit: return ans
            
            if code in visited2:
                limit = steps + queue2[0][0]
                ans = min(visited1[code] + visited2[code], ans)
            
            for i in range(4):
                d = int(code[i])
                for k in (d-1)%10, (d+1)%10:
                    cand = code[:i] + str(k) + code[i+1:]
                    if cand not in visited1 and cand not in dead:
                        visited1[cand] = steps + 1
                        queue1.append((steps+1, cand))
        return -1