Practice/Meta/Leetcode 752. Open the Lock

Leetcode 752. Open the Lock

CodingMust

Problem

You have a combination safe with 4 rotating wheels. Each wheel has 10 slots displaying digits from 0 to 9. The wheels rotate continuously, so after 9 comes 0 and before 0 comes 9. The safe starts at combination "0000".

You are given a target combination and a list of "deadend" combinations. If the safe reaches any deadend combination, it becomes permanently locked and you cannot use it anymore.

In one move, you can rotate exactly one wheel by one slot in either direction (up or down).

Determine the minimum number of moves required to reach the target combination from "0000" without passing through any deadend. If it's impossible to reach the target, return -1.

Requirements

1. Start from combination "0000"
2. Each move rotates exactly one wheel by one position (up or down)
3. Wheels wrap around: 9 + 1 = 0 and 0 - 1 = 9
4. Cannot enter or pass through any deadend combination
5. Return the minimum number of moves to reach the target, or -1 if impossible

Constraints

• 1 ≤ deadends.length ≤ 500
• deadends[i].length == 4
• target.length == 4
• target and all deadends consist of digits 0-9 only
• The target will not be "0000"

Examples

Example 1:

Input: target = "0202", deadends = ["0201","0101","0102","1212","2002"] Output: 6 Explanation: One possible shortest path is: "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"

Example 2:

Input: target = "0009", deadends = ["8888"] Output: 1 Explanation: Rotate the last wheel once: "0000" → "0009"

Example 3:

Input: target = "8888", deadends = ["0000"] Output: -1 Explanation: Cannot start because "0000" is a deadend