Word Ladder

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

题目：

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

解题思路：
这道题就是先构建好图，然后进行bfs。具体的思路如下图：


代码：

public class WordLadder {

    public static void main(String[] args){
        WordLadder wordLadder = new WordLadder();
        String start = "hit";
        String end = "cog";
        List<String> wordList = new ArrayList<>();
        String[] temp = new String[]{"hot", "dot", "dog", "lot", "log", "cog"};
        for(int i = 0; i <= temp.length - 1; i++){
            wordList.add(temp[i]);
        }
        int rst = wordLadder.ladderLength(start, end, wordList);
        System.out.println(rst);
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Set<String>> graph = construct(wordList, beginWord);
        if(!graph.containsKey(endWord)){
            return 0;
        }
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int rst = 0;
        Set<String> visited = new HashSet<>();
        while(q.size() != 0){
            int size = q.size();
            rst++;
            for(int i = 0; i <= size - 1; i++){
                String curr = q.poll();
                visited.add(curr);
                if(curr.equals(endWord)){
                    return rst;
                }
                else{
                    Set<String> set = graph.get(curr);
                    for(String next : set){
                        if(!visited.contains(next)){if(q.size() == 0){
                            return 0;
                        }
                            q.offer(next);
                        }
                    }
                }
            }
            
        }
        return rst;
    }

    private Map<String,Set<String>> construct(List<String> wordList, String beginWord) {
        String curr = beginWord;
        Map<String, Set<String>> graph = new HashMap<>();
        graph.put(curr, new HashSet<>());
        for(int i = -1; i <= wordList.size() - 1; i++){
            if(i != -1){
                curr = wordList.get(i);
                graph.put(curr, new HashSet<>());
            }
            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;
    }

}