127 Word Ladder

127. Word Ladder

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:

• Only one letter can be changed at a time
• Each intermediate word must exist in the word list

For example

Given: beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

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.

分析& 代码

把这道题想象成bfs，每次生成下次需要访问的一层，然后交替。

然后可以从两头bfs，像挖隧道一样，两边那边更少就从那边走，直到中间有汇合的点，或者两边都挖不下去了

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    if(beginWord == null || endWord == null || endWord.length() != beginWord.length() || wordList == null || wordList.size() == 0) {
        return 0;
    }
    int len = beginWord.length();
    Set<String> beginSet = new HashSet<String>();
    Set<String> endSet = new HashSet<String>();
    Set<String> visited = new HashSet<String>();
    beginSet.add(beginWord);
    endSet.add(endWord);
    visited.add(beginWord);
    int dist = 1;
    while(!beginSet.isEmpty() && !endSet.isEmpty()) {
        if(beginSet.size() > endSet.size()) {
            Set<String> temp = beginSet;
            beginSet = endSet;
            endSet = temp;
        }
        Set<String> toAdd = new HashSet<String>();
        for(String each: beginSet) {
            char[] chs = each.toCharArray();
            for(int i = 0; i < len; i++) {
                char ch = chs[i];
                for(char c = 'a'; c <= 'z'; c++) {
                    chs[i] = c;
                    String tempWord = new String(chs);
                    if(endSet.contains(tempWord)) {
                        return ++dist;
                    }
                    if(wordList.contains(tempWord) && !visited.contains(tempWord)) {
                        toAdd.add(tempWord);
                        wordList.remove(tempWord);
                        visited.add(tempWord);
                    }
                }
                chs[i] = ch;
            }
        }
        dist++;
        beginSet = toAdd;
    }
    return 0;
}