Model each combination as a graph node with edges to the 8 combinations reachable by one dial turn.

Open the Lock

hard

Acceptance: 41%

GraphsBFS

A combination lock has four dials, each cycling through digits 0-9. Starting from the combination '0000', each move turns one dial by one position (forward or backward, wrapping around). Certain combinations are deadlocked and cannot be visited. Find the minimum number of moves to reach the target combination, or -1 if it is unreachable.

Examples

Example 1:

Input:deadends = ["1000","0100","0010","0001"], target = "1111"

Output:-1

Explanation: Every single-move neighbor of '0000' is a deadend, so the target is unreachable.

Example 2:

Input:deadends = ["5555"], target = "0010"

Output:1

Explanation: Turn the third dial once: 0000 -> 0010.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Open the Lock

Examples

Hints

Related Problems