# [Search] LC 752. Open the Lock

**Goals**

- 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.

**Example 1:**

**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".

**Example 3:**

**Input:** deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

**Output:** -1

Explanation:

We can't reach the target without getting stuck.

**Strategy**

- 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)

**Highlight**

- 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

**Complexity**

- 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

**Code**

`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