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)
curr_state = start
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?
CodePudding user response：
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.
CodePudding user response：
You are adding next states to try (neighboring states) to the queue, but since you only check if new states have either already been visited, or are dead ends, you end up adding states you haven't tried yet to the queue many times. (i.e. you have no way of telling if a new state was already queued)
Basically, you're getting a bit too fancy here. A simpler implementation of the same idea:
def openLock(dead_ends: list[str], target: str, start: str = '0000') -> int:
# you could create locks with hexadecimal, alphabetic etc. disks
symbols = list(map(str, [*range(10)]))
if start in dead_ends or target in dead_ends:
return -1
elif start == target:
return 0
assert all(l == len(start) == len(target) for l in map(len, dead_ends)), \
'length of start, target and dead ends must match'
assert all(all(s in symbols for s in code) for code in dead_ends [start, target]), \
f'all symbols in start, target and dead ends must be in {symbols}'
try_neighbors = [start]
tries = {start: 0}
while try_neighbors:
state = try_neighbors.pop(0)
for i, s in enumerate(state):
for step in (-1, 1):
neighbor = state[:i] symbols[(symbols.index(s) step) % len(symbols)] state[i 1:]
if neighbor in tries:
continue
if neighbor == target:
return tries[state] 1
elif neighbor not in dead_ends:
tries[neighbor] = tries[state] 1
try_neighbors.append(neighbor)
return -1
# Provides the answer `-1` because it cannot be solved.
print(openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888"))
# Provides the answer `8` steps
print(openLock(["8887","8889","8878","8898","8788","8988","7888"], "8888"))
Your own solution with the problems fixed:
from collections import deque
def openLock(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))
# keep track of all you've seen
seen = set()
deadends = set(deadends)
while queue:
state, turns = queue.popleft()
seen.add(state)
for nb in getNeighbors(state):
# why wait for it to come up in the queue?
if nb == target:
return turns 1
if nb not in seen and nb not in deadends:
queue.append((nb, turns 1))
# add everything you've queued up to seen
seen.add(nb)
return -1
print(openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888"))