Open the Lock BFS

Find the minimum number of wheel turns to reach a target combination, avoiding deadends.

bfs strings graph queue

You have a lock with 4 circular wheels, each wheel has 10 slots: '0' through '9' in order. Each move consists of turning one wheel one slot forward or backward (e.g., '9' → '0' forward or '0' → '9' backward). The lock initially shows '0000'. Given a list of deadends (strings of 4 digits), if the lock ever reaches any deadend, it immediately jams and cannot be opened. Given a target string target representing the combination that opens the lock, implement the function `openLock(deadends, target)` that returns the minimum total number of turns required to open the lock, or -1 if it is impossible.

Write the function signature:

```python
def openLock(deadends: list[str], target: str) -> int:
```

Constraints

1 <= len(deadends) <= 500
deadends[i] and target are strings of length 4 consisting of digits '0'-'9'
target is not in deadends

Example

>>> openLock(["0201","0101","0102","1212","2002"], "0202")
6
>>> openLock(["8888"], "0009")
1
>>> openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888")
-1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Model each 4-digit combination as a node in an unweighted graph. Edges connect states that differ by one wheel turn.

Use BFS from '0000' and count the number of turns (levels). Stop when you pop the target. If the start '0000' is in deadends, return -1 immediately.

To generate neighbors, for each position in the 4-digit string, try +1 and -1 modulo 10.

Track visited states to avoid revisiting, and skip any neighbor that is in the deadends set.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.