Word Ladder2

题目地址：
https://leetcode.com/problems/word-ladder-ii/description/

题目：

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

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

解题思路：
这道题用bfs来解。

代码：

public class WordLadder2 {

    /*        Given:        beginWord = "hit"        endWord = "cog"        wordList = ["hot","dot","dog","lot","log","cog"]        Return          [            ["hit","hot","dot","dog","cog"],            ["hit","hot","lot","log","cog"]          ]     */
    public static void main(String[] args){
        WordLadder2 wordLadder2 = new WordLadder2();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");
        List<List<String>> rst = wordLadder2.findLadders(beginWord, endWord, wordList);
        System.out.println(rst);
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> rst = new ArrayList<>();
        List<String> list = new ArrayList<>();
        Map<String, List<String>> map = buildMap(wordList, beginWord);
        Deque<String> q = new LinkedList<>();
        q.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        list.add(beginWord);
        Deque<List<String>> paths = new LinkedList<>();
        boolean done = false;
        // count how many level we have        int count = 0;
        while(q.size() != 0 && !done){
            int size = q.size();
            count++;
            for(int i = 0; i <= size - 1; i++){
                String curr = q.poll();
                // add to visited                visited.add(curr);
                List<String> level = map.get(curr);

                List<String> temp = paths.poll();
                for(int j = 0; j <= level.size() - 1; j++){
                    if(visited.contains(level.get(j))){
                        continue;
                    }
                    if(level.get(j).equals(endWord)){
                        done = true;
                    }
                    List<String> tempPath = new ArrayList<>(temp);
                    tempPath.add(level.get(j));
                    paths.offer(tempPath);
                    q.offer(level.get(j));

                    // remove unneccesary part                    if(map.get(level.get(j)).contains(curr)){
                        map.get(level.get(j)).remove(curr);
                    }

                }
            }
        }
        while(paths.size() != 0){
            List<String> curr = paths.poll();
            if(curr.size() == count + 1 && curr.get(curr.size() - 1).equals(endWord)){
                rst.add(curr);
            }
        }
        return rst;
    }

    private Map<String,List<String>> buildMap(List<String> wordList, String beginWord) {
        String curr = beginWord;
        Map<String, List<String>> graph = new HashMap<>();
        graph.put(curr, new ArrayList<>());
        for(int i = -1; i <= wordList.size() - 1; i++){
            // new a arraylist for that string            if(i != -1){
                curr = wordList.get(i);
                graph.put(curr, new ArrayList<>());
            }
            for(int j = 0; j <= wordList.size() - 1; j++){
                String other = wordList.get(j);
                if(curr.equals(other)){
                    continue;
                }
                else{
                    if(isNext(curr, other)){
                        graph.get(curr).add(other);
                    }
                }
            }
        }
        return graph;
    }

    private boolean isNext(String curr, String other) {
        int i = 0;
        int rst = 0;
        while(i <= curr.length() - 1){
            if(curr.charAt(i) != other.charAt(i)){
                rst++;
            }
            if(rst >= 2){
                return false;
            }
            i++;
        }
        return true;
    }

}