Open the Lock

Open the Lock is LeetCode problem 752, commonly tagged with BFS, Array, Hash Table, and String, and frequently asked in Microsoft interviews.[7]

Problem Statement

You have a lock with 4 circular wheels, each with 10 slots labeled '0' through '9'. The wheels rotate freely and wrap around (9 to 0, 0 to 9). Start from "0000". A list of deadends cannot be stopped on. Return the minimum turns to reach the target; -1 if impossible.[1][7]

Examples

Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1

Example 3:
Input: deadends = ["8887","8889","8878","9","8787","7878","8989","7888","8888"], target = "8888"
Output: -1[7]

Constraints

• 1 ≤ deadends.length ≤ 500
• deadends[i].length == 4
• target.length == 4
• target does not appear in deadends.
• target and deadends[i] consist of digits 0-9.[5][7]