CONY的世界

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:

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

這題是用 bidirectional BFS 來加速，從頭尾set來找尋是否存在路徑，因為雙向的關係，所以搜尋的範圍從本來的d 變成d/2，原本是O(K^d) 變小成O( 2*K^(d/2)) => O( K^(d/2))

至於visitedSet 不用想得太複雜，只要能出現其實就可以移除了，因為你不會想繞了一大圈結果才變成早就可以出現的word，所以一旦能出現就越早出現，然後之後就不用再考慮了

額外注意的點之一是，wordList 這邊是List<String>，但是這個search 的速度是O(n)，所以一開始就被它轉成Set ，降低搜尋的複雜度

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        HashSet<String> beginSet = new HashSet();
        HashSet<String> endSet = new HashSet();
        HashSet<String> visitedSet = new HashSet();
        HashSet<String> wordset = new HashSet(wordList);
        
        int strlen = beginWord.length();
        
        beginSet.add(beginWord);
        if(wordset.contains(endWord)){
            endSet.add(endWord); 
            wordset.remove(endWord);
        } else return 0;
        int len=1;
        while(!beginSet.isEmpty() && !endSet.isEmpty()){
            if(beginSet.size() > endSet.size()){
                HashSet<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            } 
            HashSet<String> tmp = new HashSet();
            for(String s:beginSet){
                char[] word = s.toCharArray();
                for(int index = 0; index < strlen; index++){
                    char old = word[index];
                    for(char c='a';c<='z'; c++){
                        word[index] = c;
                        String ss = String.valueOf(word);
                        if(endSet.contains(ss))
                            return len+1;
                        if(!visitedSet.contains(ss) && wordset.contains(ss)) {
                            tmp.add(ss);
                            visitedSet.add(ss);
                            wordset.remove(ss);
                        }      
                    }          
                    word[index] = old;
                }
            }    
            beginSet = tmp;
            len++;
        }
        return 0;
    }
}