[Search] LC 752. Open the Lock

  • Given a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'.
  • The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
  • The lock initially starts at '0000', a string representing the state of the 4 wheels.
  • Also given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
  • Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.
  • Search + BFS
  • Use BFS to explore, in each round we tweak each of the 4 slot by +1 or -1
  • Skip (continue) the search when the current string is in deadends or has visited
  • A trick to perform the +1 & -1 operations:
for j in [-1,1]:
str((int(curr[i])+j+10)%10)
  • A graph BFS problem to find the shortest path!
  • BFS indeed guarantees the shortest path because we are exploring all the available options in each iteration
  • Time: O(8*10⁴); 8 = 4*2 because we have 4 slots, and 2 options each search (+1 or -1); 10⁴ because we have 4 slots, and there are 10 possible options in each search
  • Space: O(10⁴+D); 10⁴ represents all the possible combinations; with D = size of the deadends array
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
start = '0000'
if target == start:
return 0
dead = set(deadends)
if start in dead:
return -1

q = deque([(start, 0)])
v = set(start)

while q:
curr, step = q.popleft()

for i in range(0,4):
for j in [-1,1]:
nxt= curr[:i] + str((int(curr[i])+j+10)%10) + curr[i+1:]
if nxt == target:
return step+1
if nxt in dead or nxt in v:
continue

q.append((nxt, step+1))
v.add(nxt)

return -1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store