1
class Solution {
2
  public int openLock(String[] deadends, String target) {
3
    // Converted target to Integer type.
4
    int t = Integer.parseInt(target);
5
    HashSet<Integer> visited = new HashSet<>();
6

7
    // Converting deadend strings to Integer type. To prevent from visiting deadend, we already mark
8
    // them visited.
9
    for (String str : deadends) {
10
      visited.add(Integer.parseInt(str));
11
    }
12
    // BFS
13
    Queue<Integer> q = new ArrayDeque<>();
14
    // We make sure that 0 itself isn't a deadend
15
    if (visited.contains(0)) {
16
      return -1;
17
    }
18
    q.add(0);
19
    visited.add(0);
20
    int level = 0;
21
    while (q.size() > 0) {
22
      int size = q.size();
23
      while (size-- > 0) {
24
        int elem = q.remove();
25
        if (t == elem) {
26
          return level;
27
        }
28
        // Will help check 4 digits of the element. From digit with low precendence(ones place) to
29
        // high precedence(thousands place)
30
        for (int i = 1; i < 10000; i = i * 10) {
31
          // The wheel can be rotated in two directions. Hence two numbers.
32
          int num1;
33
          int num2;
34
          // The wheel at 0 can become 1 or 9 due to wrapping.
35
          if (elem / i % 10 == 0) {
36
            num1 = elem + i;
37
            num2 = elem + i * 9;
38
          }
39
          // The wheel at 9 can become 0 or 8 due to wrapping.
40
          else if (elem / i % 10 == 9) {
41
            num1 = elem - i * 9;
42
            num2 = elem - i;
43
          } else {
44
            num1 = elem - i;
45
            num2 = elem + i;
46
          }
47
          // Checking if numbers have already been visited.
48
          if (!(visited.contains(num1))) {
49
            visited.add(num1);
50
            q.add(num1);
51
          }
52
          if (!(visited.contains(num2))) {
53
            visited.add(num2);
54
            q.add(num2);
55
          }
56
        }
57
      }
58
      level++;
59
    }
60
    return -1;
61
  }
62
}