I'm trying to solve the leetcode question https://leetcode.com/problems/open-the-lock/ with BFS and came up with the approach below.
def openLock(self, deadends: List[str], target: str): -> int
def getNeighbors(node) ->List[str]:
neighbors = []
dirs = [-1, 1]
for i in range(len(node)):
for direction in dirs:
x = (int(node[i]) + direction) % 10
neighbors.append(node[:i] + str(x) + node[i+1:])
return neighbors
start = '0000'
if start in deadends:
return -1
queue = deque()
queue.append((start, 0))
turns = 0
visited = set()
deadends = set(deadends)
while queue:
state, turns = queue.popleft()
visited.add(state)
if state == target:
return turns
for nb in getNeighbors(state):
if nb not in visited and nb not in deadends:
queue.append((nb, turns+1))
return -1
However this code runs into a Time Limit Exceeded exception and it only passes 2/48 of the test cases. For ex. with a testcase where the deadends are ["8887","8889","8878","8898","8788","8988","7888","9888"] and the target is "8888" (the start is always "0000") my solution TLE. I notice that if I essentially change one line and add neighboring nodes to the visited set in my inner loop, my solution passes that test case and all other test cases.
for nb in getNeighbors(state):
if nb not in visited and nb not in deadends:
visited.add(nb)
queue.append((nb, turns+1))
My while loop then becomes
while queue:
state, turns = queue.popleft()
if state == target:
return turns
for nb in getNeighbors(state):
if nb not in visited and nb not in deadends:
visited.add(nb)
queue.append((nb, turns+1))
Can someone explain why the first approach runs into TLE while the second doesn't?
Yes. Absolutely. You need to add the item to visited when it gets added to the queue the first time, not when it gets removed from the queue. Otherwise your queue is going to grow exponentially.
Let's look at say 1111. Your code is going to add 1000, 0100, 0010, 0001 (and others) to the queue. Then your code is going to add each of 1100, 1010, 1001, 0110, 0101, 0011, and others twice because they are neighbors of two elements in the queue, and they haven't been visited yet. And then you add each of 1110, 1101, 1011, 0111 four times. If instead you're searching for 5555, you'll have many many duplicates on your queue.
Change the name of your visited variable to seen. Notice that once an item has been put on the queue, it never needs to be put on the queue again.
Seriously, try searching for 5555 with no dead ends. When you find it, look at the queue and see how many elements are on the queue, versus how many distinct elements are on the queue.