Turning a Combination Lock

Medium

A combination lock has four wheels, each showing the digits 0 to 9 in a circle: 9 is followed by 0 and vice versa. One move turns one wheel by one digit forward or backward. The lock currently shows "0000". The list jams holds combinations that jam the lock: once it shows any of them, the wheels will not turn again. Return the fewest moves needed to dial code without ever landing on a jamming combination, or -1 if that is impossible.

Example 1

jams=["0010", "0090"], code="0011" → 2

The third wheel cannot be turned first: both 0010 and 0090 jam the lock. Turn the fourth one first, 0000 → 0001, then the third, 0001 → 0011. Two turns.

Example 2

jams=["5555"], code="9000" → 1

Turn the first wheel backwards: 0 → 9 in one move.

Example 3

jams=["0001", "0009", "0010", "0090", "0100", "0900", "1000", "9000"], code="1234" → -1

All eight positions next to 0000 jam the lock, so it cannot move at all.

Constraints

0 ≤ len(jams) ≤ 500
Every string in jams and code is exactly 4 digits
code is not in jams

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Hash Table String

Similar problems

Merge Contact Cards Medium Chains of Synonyms Medium Rearrange Through Links Medium Smallest Shared Territory Medium Expand a Template With Variables Medium

Input

jams=["0010", "0090"], code="0011"

Expected

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.