|
1 | | -//Simple BFS solution |
2 | | - |
3 | 1 | classSolution { |
4 | | - |
5 | 2 | publicintopenLock(String[]deadends,Stringtarget) { |
6 | | -Stringstart ="0000"; |
7 | | -intans =0; |
8 | | -Queue<String>q =newLinkedList<>(); |
9 | | -HashSet<String>visited =newHashSet<>(); |
10 | | -//Add all the deadends in the visited set so we can ignore them and visited values altogether. |
11 | | -for (Strings :deadends)visited.add(s); |
12 | | -q.offer(start); |
13 | | -while (!q.isEmpty()) { |
14 | | -intsize =q.size(); |
15 | | -for (intj =0;j <size;j++) { |
16 | | -Stringstr =q.poll(); |
17 | | -StringBuildercur =newStringBuilder(str); |
18 | | -if (str.equals(target))returnans; |
19 | | -if (!visited.contains(cur.toString())) { |
20 | | -for (inti =0;i <start.length();i++) { |
21 | | -//edge case for 0 |
22 | | -if (cur.charAt(i) =='0') { |
23 | | -cur.setCharAt(i,'1'); |
24 | | -q.offer(cur.toString()); |
25 | | -cur.setCharAt(i,'9'); |
26 | | -q.offer(cur.toString()); |
27 | | - }elseif (cur.charAt(i) =='9') {//edge case for 9 |
28 | | -cur.setCharAt(i,'0'); |
29 | | -q.offer(cur.toString()); |
30 | | -cur.setCharAt(i,'8'); |
31 | | -q.offer(cur.toString()); |
32 | | - }else { |
33 | | -cur.setCharAt(i, ((char) (cur.charAt(i) +1))); |
34 | | -q.offer(cur.toString()); |
35 | | -cur.setCharAt(i, ((char) (cur.charAt(i) -2))); |
36 | | -q.offer(cur.toString()); |
37 | | - } |
38 | | -visited.add(str); |
39 | | -cur.setLength(0); |
40 | | -cur.append(str); |
| 3 | +Set<String>visited =newHashSet<>(); |
| 4 | +for (Stringdeadend :deadends) { |
| 5 | +if (deadend.equals("0000")) { |
| 6 | +return -1; |
| 7 | + } |
| 8 | +visited.add(deadend); |
| 9 | + } |
| 10 | + |
| 11 | +Queue<String>queue =newLinkedList<>(); |
| 12 | +queue.offer("0000"); |
| 13 | +visited.add("0000"); |
| 14 | + |
| 15 | +intturns =0; |
| 16 | +while (!queue.isEmpty()) { |
| 17 | +intsize =queue.size(); |
| 18 | +for (inti =0;i <size;i++) { |
| 19 | +Stringlock =queue.poll(); |
| 20 | +if (lock.equals(target)) { |
| 21 | +returnturns; |
| 22 | + } |
| 23 | +List<String>children =generateChildren(lock); |
| 24 | +for (Stringchild :children) { |
| 25 | +if (!visited.contains(child)) { |
| 26 | +visited.add(child); |
| 27 | +queue.offer(child); |
41 | 28 | } |
42 | 29 | } |
43 | 30 | } |
44 | | -ans++; |
| 31 | +turns++; |
45 | 32 | } |
46 | 33 | return -1; |
47 | 34 | } |
| 35 | + |
| 36 | +privateList<String>generateChildren(Stringlock) { |
| 37 | +List<String>children =newArrayList<>(); |
| 38 | +for (inti =0;i <4;i++) { |
| 39 | +char[]digits =lock.toCharArray(); |
| 40 | +digits[i] = (char)(((digits[i] -'0' +1) %10) +'0'); |
| 41 | +children.add(newString(digits)); |
| 42 | +digits[i] = (char)(((digits[i] -'0' -2 +10) %10) +'0'); |
| 43 | +children.add(newString(digits)); |
| 44 | + } |
| 45 | +returnchildren; |
| 46 | + } |
48 | 47 | } |