LC 0752 [M] Open the Lock - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=Pzg3bCDY87w&ab_channel=NeetCode
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if '0000' in deadends:
return -1
def children(lock):
res = []
for i in range(4): # for each of all 4 numbers
# increment it
digit = str((int(lock[i]) + 1) % 10)
res.append(lock[:i] + digit + lock[i+1:])
# or decrement it
digit = str((int(lock[i]) - 1) % 10)
res.append(lock[:i] + digit + lock[i+1:])
return res
Q = deque()
Q.append( ['0000', 0] ) # [lock, turns]
visited = set(deadends)
while Q:
lock, turns = Q.popleft()
if lock == target:
return turns
for child in children(lock):
if child not in visited:
Q.append( [child, turns + 1] )
visited.add(child)
return -1