|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -importjava.util.ArrayList; |
4 | | -importjava.util.List; |
| 3 | +importjava.util.*; |
5 | 4 |
|
6 | 5 | /** |
7 | 6 | * 126. Word Ladder II |
|
32 | 31 | You may assume beginWord and endWord are non-empty and are not the same. |
33 | 32 | */ |
34 | 33 | publicclass_126 { |
| 34 | +/**Reference: https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj*/ |
35 | 35 |
|
36 | | -publicList<List<String>>findLadders(StringbeginWord,StringendWord,List<String>wordList) { |
37 | | -List<List<String>>result =newArrayList<>(); |
38 | | -returnresult; |
| 36 | +Map<String,List<String>>map; |
| 37 | +List<List<String>>results; |
| 38 | + |
| 39 | +publicList<List<String>>findLadders(Stringstart,Stringend,List<String>dict) { |
| 40 | +results =newArrayList<>(); |
| 41 | +if (dict.size() ==0) |
| 42 | +returnresults; |
| 43 | + |
| 44 | +intmin =Integer.MAX_VALUE; |
| 45 | + |
| 46 | +Queue<String>queue =newArrayDeque<>(); |
| 47 | +queue.add(start); |
| 48 | + |
| 49 | +map =newHashMap<>(); |
| 50 | + |
| 51 | +Map<String,Integer>ladder =newHashMap<>(); |
| 52 | +for (Stringstring :dict) |
| 53 | +ladder.put(string,Integer.MAX_VALUE); |
| 54 | +ladder.put(start,0); |
| 55 | + |
| 56 | +dict.add(end); |
| 57 | +//BFS: Dijisktra search |
| 58 | +while (!queue.isEmpty()) { |
| 59 | + |
| 60 | +Stringword =queue.poll(); |
| 61 | + |
| 62 | +intstep =ladder.get(word) +1;//'step' indicates how many steps are needed to travel to one word. |
| 63 | + |
| 64 | +if (step >min)break; |
| 65 | + |
| 66 | +for (inti =0;i <word.length();i++) { |
| 67 | +StringBuilderbuilder =newStringBuilder(word); |
| 68 | +for (charch ='a';ch <='z';ch++) { |
| 69 | +builder.setCharAt(i,ch); |
| 70 | +Stringnew_word =builder.toString(); |
| 71 | +if (ladder.containsKey(new_word)) { |
| 72 | + |
| 73 | +if (step >ladder.get(new_word)) {//Check if it is the shortest path to one word. |
| 74 | +continue; |
| 75 | + }elseif (step <ladder.get(new_word)) { |
| 76 | +queue.add(new_word); |
| 77 | +ladder.put(new_word,step); |
| 78 | + }else ;// It is a KEY line. If one word already appeared in one ladder, |
| 79 | +// Do not insert the same word inside the queue twice. Otherwise it gets TLE. |
| 80 | + |
| 81 | +if (map.containsKey(new_word)) {//Build adjacent Graph |
| 82 | +map.get(new_word).add(word); |
| 83 | + }else { |
| 84 | +List<String>list =newLinkedList<String>(); |
| 85 | +list.add(word); |
| 86 | +map.put(new_word,list); |
| 87 | +//It is possible to write three lines in one: |
| 88 | +//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word}))); |
| 89 | +//Which one is better? |
| 90 | + } |
| 91 | + |
| 92 | +if (new_word.equals(end)) { |
| 93 | +min =step; |
| 94 | + } |
| 95 | + |
| 96 | + }//End if dict contains new_word |
| 97 | + }//End:Iteration from 'a' to 'z' |
| 98 | + }//End:Iteration from the first to the last |
| 99 | + }//End While |
| 100 | + |
| 101 | +//BackTracking |
| 102 | +LinkedList<String>result =newLinkedList<>(); |
| 103 | +backTrace(end,start,result); |
| 104 | + |
| 105 | +returnresults; |
| 106 | + } |
| 107 | + |
| 108 | +privatevoidbackTrace(Stringword,Stringstart,List<String>list) { |
| 109 | +if (word.equals(start)) { |
| 110 | +list.add(0,start); |
| 111 | +results.add(newArrayList<>(list)); |
| 112 | +list.remove(0); |
| 113 | +return; |
| 114 | + } |
| 115 | +list.add(0,word); |
| 116 | +if (map.get(word) !=null) { |
| 117 | +for (Strings :map.get(word)) { |
| 118 | +backTrace(s,start,list); |
| 119 | + } |
| 120 | + } |
| 121 | +list.remove(0); |
39 | 122 | } |
40 | 123 |
|
41 | 124 | } |