Leetcoder - Word Ladder II

 Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end,
HashSet<String> dict) {
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);
HashMap<String, ArrayList<String>> backTrack = new HashMap<String, ArrayList<String>>();

ArrayList<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
while (true) {
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
HashSet<Integer> skip = new HashSet<Integer>();
    if(backTrack.containsKey(str)) {
for(String p : backTrack.get(str)) {
for(int i=0;i<p.length();i++) {
if(p.charAt(i)!=str.charAt(i)) {
skip.add(i);
}
}
}
}
                ArrayList<String> nexts = new ArrayList<String>();
    for (int i = 0; i < str.length(); i++) {
if(skip.contains(i)) {
continue;
}
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
ArrayList<String> preNode = backTrack.get(next);
if (preNode == null) {
preNode = new ArrayList<String>();
backTrack.put(next, preNode);
}
preNode.add(str);
if (next.equals(end)) {
find = true;
} else {
newFronties.add(next);
}
}
}
if (find || fronties.size() == 0) {
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
if (find) {
ArrayList<String> initPath = new ArrayList<String>();
initPath.add(end);
this.findPath(initPath, backTrack, paths, end);
}
return paths;
}

private void findPath(ArrayList<String> tmp, HashMap<String, ArrayList<String>> backTrack,
ArrayList<ArrayList<String>> paths, String next) {
ArrayList<String> parents = backTrack.get(next);
if (parents != null) {
for (String p : parents) {
tmp.add(p);
this.findPath(tmp, backTrack, paths, p);
tmp.remove(tmp.size()-1);
}
} else {
ArrayList<String> path = new ArrayList<String>();
for(int i=tmp.size()-1;i>=0;i--) {
path.add(tmp.get(i));
}
paths.add(path);
}
}
}




=============


public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if (start == null || end == null || wordList == null || wordList.size() == 0) {
            return res;
        }
        HashMap<String, List<String>> map = new HashMap<>();
        wordList.add(end);
        HashSet<String> queue = new HashSet<String>();
        queue.add(start);
        boolean find = false;
        while (!queue.isEmpty() && !wordList.isEmpty() && !find) {
            int count = queue.size();
            HashSet<String> nextLevel = new HashSet<String>();
            for (String word : queue) {
                for (int i = 0; i < word.length(); i++) {
                    char cs[] = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (word.charAt(i) == c) {
                            continue;
                        }
                        cs[i] = c;
                        String nextWord = new String(cs);
                        if (end.equals(nextWord)) {
                            find = true;
                        }
                        if (wordList.contains(nextWord)) {
                            List<String> pres = map.get(nextWord);
                            if (pres == null) {
                                pres = new ArrayList<String>();
                                map.put(nextWord, pres);
                            }
                            pres.add(word);
                            nextLevel.add(nextWord);
                        }
                    }
                    cs[i] = word.charAt(i);
                }
            }
            for (String str : nextLevel) {
                wordList.remove(str);
            }
            queue = nextLevel;
        }
        if (!find) {
            return res;
        }
        helper(start, map, new ArrayList<String>(), end, res);
        return res;
    }
   
    private void helper(String start, HashMap<String, List<String>> map, List<String> curList, String word, List<List<String>> res) {
        if (word.equals(start)) {
            List<String> newList = new ArrayList<String>(curList);
            newList.add(word);
            Collections.reverse(newList);
            res.add(newList);
        } else {
            curList.add(word);
            List<String> pres = map.get(word);
            for (String pre : pres) {
                helper(start, map, curList, pre, res);
            }
            curList.remove(curList.size() - 1);
        }
    }
}