format

fishercoder1534 · fishercoder1534 · commit e320d72d728e · 2017-07-27T20:32:09.000-07:00
diff --git a/README.md b/README.md
@@ -444,6 +444,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |130|[Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_130.java)| O(?)|O(?) | Medium|
 |129|[Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_129.java)| O(n)|O(h) | Medium| DFS
 |127|[Word Ladder](https://leetcode.com/problems/word-ladder/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_127.java)| O(?)|O(?) | Medium| BFS
+|126|[Word Ladder II](https://leetcode.com/problems/word-ladder-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_126.java)| O(?)|O(?) | Hard| BFS
 |125|[Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_125.java)| O(n)|O(1) | Easy| Two Pointers
 |124|[Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_124.java)| O(n)|O(h) | Hard | Tree, DFS
 |123|[Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_123.java)| O(?)|O(?) | Hard |
diff --git a/src/main/java/com/fishercoder/solutions/_126.java b/src/main/java/com/fishercoder/solutions/_126.java
@@ -1,7 +1,6 @@
 package com.fishercoder.solutions;
 
-import java.util.ArrayList;
-import java.util.List;
+import java.util.*;
 
 /**
  * 126. Word Ladder II
@@ -32,10 +31,94 @@
  You may assume beginWord and endWord are non-empty and are not the same.
  */
 public class _126 {
+    /**Reference: https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj*/
 
-    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
-        List<List<String>> result = new ArrayList<>();
-        return result;
+    Map<String, List<String>> map;
+    List<List<String>> results;
+
+    public List<List<String>> findLadders(String start, String end, List<String> dict) {
+        results = new ArrayList<>();
+        if (dict.size() == 0)
+            return results;
+
+        int min = Integer.MAX_VALUE;
+
+        Queue<String> queue = new ArrayDeque<>();
+        queue.add(start);
+
+        map = new HashMap<>();
+
+        Map<String, Integer> ladder = new HashMap<>();
+        for (String string : dict)
+            ladder.put(string, Integer.MAX_VALUE);
+        ladder.put(start, 0);
+
+        dict.add(end);
+        //BFS: Dijisktra search
+        while (!queue.isEmpty()) {
+
+            String word = queue.poll();
+
+            int step = ladder.get(word) + 1;//'step' indicates how many steps are needed to travel to one word.
+
+            if (step > min) break;
+
+            for (int i = 0; i < word.length(); i++) {
+                StringBuilder builder = new StringBuilder(word);
+                for (char ch = 'a'; ch <= 'z'; ch++) {
+                    builder.setCharAt(i, ch);
+                    String new_word = builder.toString();
+                    if (ladder.containsKey(new_word)) {
+
+                        if (step > ladder.get(new_word)) {//Check if it is the shortest path to one word.
+                            continue;
+                        } else if (step < ladder.get(new_word)) {
+                            queue.add(new_word);
+                            ladder.put(new_word, step);
+                        } else ;// It is a KEY line. If one word already appeared in one ladder,
+                        // Do not insert the same word inside the queue twice. Otherwise it gets TLE.
+
+                        if (map.containsKey(new_word)) {//Build adjacent Graph
+                            map.get(new_word).add(word);
+                        } else {
+                            List<String> list = new LinkedList<String>();
+                            list.add(word);
+                            map.put(new_word, list);
+                            //It is possible to write three lines in one:
+                            //map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
+                            //Which one is better?
+                        }
+
+                        if (new_word.equals(end)) {
+                            min = step;
+                        }
+
+                    }//End if dict contains new_word
+                }//End:Iteration from 'a' to 'z'
+            }//End:Iteration from the first to the last
+        }//End While
+
+        //BackTracking
+        LinkedList<String> result = new LinkedList<>();
+        backTrace(end, start, result);
+
+        return results;
+    }
+
+    private void backTrace(String word, String start, List<String> list) {
+        if (word.equals(start)) {
+            list.add(0, start);
+            results.add(new ArrayList<>(list));
+            list.remove(0);
+            return;
+        }
+        list.add(0, word);
+        if (map.get(word) != null) {
+            for (String s : map.get(word)) {
+                backTrace(s, start, list);
+            }
+        }
+        list.remove(0);
     }
 
 }
