126 Word Ladder II

126
Word Ladder II
13.2%
Hard
所有的words可以组成一张图。节点是word，如果有一个字母不一样，那么这两个节点之间有一条边。
可以从start -> end （找到后的添加顺序是end->start），也可以end->start(添加顺序相反,start->end)
hashmap存查找的路径
end-> start

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> wordList) {
        //search from end to start
        List<List<String>> rst = new ArrayList<List<String>>();
        wordList.remove(end);
        wordList.add(start);
        HashMap<String, ArrayList<String>> path = new HashMap<String, ArrayList<String>>();
        path.put(end, null);
        HashMap<String, ArrayList<String>> pathHasAdded = new HashMap<String, ArrayList<String>>();
        pathHasAdded.put(end, null);
        while (!path.containsKey(start)){
            HashMap<String, ArrayList<String>> pathToBeAdded = new HashMap<String, ArrayList<String>>();
            for (String word:pathHasAdded.keySet()){
                ArrayList<String> neighbourWords = neighbourWords(word);
                for (String nword:neighbourWords){
                    if (!path.containsKey(nword) && wordList.contains(nword)){
                        if (!pathToBeAdded.containsKey(nword)) pathToBeAdded.put(nword, new ArrayList<String>());
                        pathToBeAdded.get(nword).add(word);
                    }
                }
            }
            if (pathToBeAdded.isEmpty()) return rst;
            path.putAll(pathToBeAdded);
            pathHasAdded = pathToBeAdded;
        }
        LinkedList<String> output = new LinkedList<String>();
        output.add(start);
        dfs(rst, path, output,end);
        return rst;
    }
    private ArrayList<String> neighbourWords(String word){
        ArrayList<String> rst = new ArrayList<String>();
        char[] charArray = word.toCharArray();
        for (int i=0; i<word.length();i++){
            char bakChar = charArray[i];
            for (char varChar = 'a'; varChar<='z'; varChar++){
                charArray[i] = varChar;
                String varString = new String(charArray);
                rst.add(varString);
            }
            charArray[i] = bakChar;
        }
        return rst;
    } 
    private void dfs(List<List<String>> rst, HashMap<String, ArrayList<String>> map, LinkedList<String> output, String end){
        if (output.getLast().equals(end)){
            rst.add((List<String>)output.clone());
            return;
        }
        for (String nextWord:map.get(output.getLast())){
            output.addLast(nextWord);
            dfs(rst, map, output, end);
            output.removeLast();
        }
    }
}

start->end

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        dict.add(end);
        dict.remove(start);
        HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();
        // (a,b,c) -> d
        HashSet<String> currSearch = new HashSet<String>();
        currSearch.add(start);
        while (!currSearch.isEmpty()){
            HashSet<String> nextSearch = new HashSet<String>();
            for (String s:currSearch){
                ArrayList<String> sList = transform(s);
                for (String sNext:sList){
                    if (dict.contains(sNext)){
                        if (!map.containsKey(sNext)) map.put(sNext,new ArrayList<String>());
                        map.get(sNext).add(s);
                        nextSearch.add(sNext);
                    }
                }
            }
            if (nextSearch.contains(end)) break;
            dict.removeAll(nextSearch);
            currSearch = nextSearch;
        }
        List<List<String>> rst = new ArrayList<List<String>>();
        if (!map.containsKey(end)) return rst;
        LinkedList<String> output = new LinkedList<String>();
        output.addFirst(end);
        dfs(rst,map,output,start);
        return rst;
    }
    private ArrayList<String> transform(String s){
        char[] cha = s.toCharArray();
        ArrayList<String> list = new ArrayList<String>();
        for (int i=0; i<cha.length; i++){
            char bak = cha[i];
            for (char j='a'; j<='z'; j++){
                cha[i] = j;
                list.add(new String(cha));
            }
            cha[i] = bak;
        }
        return list;
    }
    private void dfs(List<List<String>> rst, HashMap<String,ArrayList<String>> map, LinkedList<String> output, String start){
        if (output.getFirst().equals(start)){
            rst.add((List<String>)output.clone());
            return;
        }
        for (String prevString:map.get(output.getFirst())){
            output.addFirst(prevString);
            dfs(rst,map,output,start);
            output.removeFirst();
        }
    }
}