prep-coding/leetcode/OpenLock.java at master · tushar-sharma/prep-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

class Solution {

    public int openLock(String[] deadends, String target) {

        int minimumTurns = -1;

        String start = "0000";

        Set<String> visited = new HashSet<>();

        for (String deadend : deadends){
            visited.add(deadend);
        }

        Deque<String> queue = new ArrayDeque<>();
        queue.offer(start);

        int countWays = 0;

        while (!queue.isEmpty()){

            int size = queue.size();

            while (size > 0 ) {

                String currentStart = queue.poll();


                if (visited.contains(currentStart)){
                    size--;
                    continue;
                }


                if (target.equals(currentStart)){
                    return countWays;
                }

                StringBuilder sb = new StringBuilder(currentStart);

                for (int i = 0; i < 4; i++){

                    char currentStartChar =  sb.charAt(i);

                    String upCurrentStart = currentStart.substring(0, i) + (currentStartChar == '9' ? 0 :(currentStartChar - '0' + 1) ) + currentStart.substring(i + 1);

                    String downCurrentStart = currentStart.substring(0, i) + (currentStartChar == '0' ? 9 : (currentStartChar - '0' - 1) ) + currentStart.substring(i + 1);

                    if (!visited.contains(upCurrentStart)) {
                        queue.offer(upCurrentStart);
                    }

                    if (!visited.contains(downCurrentStart)){
                        queue.offer(downCurrentStart);
                    }
                }

                visited.add(currentStart);

                size --;

            }

            countWays++;

        }


        return minimumTurns;

    }
}

/**
  Remember :
  1. increment a character in string
     e.g. char a = 'a';
          char b = (char) (a + 1);

    Alternatively

          char a = 'a';
          String b  = "" + (a - '0' + 1);


  2. ASCII values for 0 is 48 and 9 is 57
                      a is 97 and z is 122
                      A is 65 and Z is 90

  3. Modifiy a character in a string at location i
     e.g. String newText = text.substring(0, i) + modifiedChar + text.substring(i + 1);

  4. think BFS when calculating *minimum*

  5. Offer and poll with Queue using ArrayDeque

  6. Simple BFS template

      queue = queue()

      queue.offer(value)

      while (! queue is not empty):

          size = queue.size

          while (size > 0 )

              value = queue.poll()


              if not visited
                  queue.offer(value)

              size--

 */