127. Word Ladder

problem 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:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. 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. Example 1:

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

Output: 5

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

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

algorithm thought

这里需要用一种搜索方法找到找到最短路径，对于这种需求，有一种遍历方式能完美的契合。那就是广度优先搜索。找到第一个叶子节点，也就是第一个到达endWord的路径就是最短路径。我们从beginWord开始，每次将beginWord能到的下一个单词加入队列中，然后将他们从wordlist中删除，重复操作，直到到endWord或者没有结果。

code

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string>wordlists(wordList.begin(),wordList.end());
        return ladder(beginWord,endWord,wordlists); 
    }
    int ladder(string&beginword, string&endword, unordered_set<string>& wordlists) {
        int res=2;
        string pos=" ";
        queue<string> next;
        nextword(next,beginword,wordlists);
        next.push(pos);
        while(!next.empty()){
            string word=next.front();
            next.pop();
            if(word==pos){
                if(next.empty())
                    break;
                res++;
                next.push(pos);
            }    
            if(word==endword)
                return res;
            nextword(next,word,wordlists);
        }
        return 0;
    }
    void nextword(queue<string>&next,string&beginword,unordered_set<string>& wordlists){
         for(int i=0;i<beginword.size();++i){
             char pre=beginword[i];
             for(int j=0;j<26;++j){
                 beginword[i]=char('a'+j);
                 if(wordlists.count(beginword)){
                     next.push(beginword);
                     wordlists.erase(beginword);
                 }
             }
             beginword[i]=pre;
         }
    }
};

algorithm analysis

这里涉及到很多复杂的操作，找到nextword，需要进行26*n次，很多情况下，n是小于26的，所以这里几乎时间复杂度是O(n²)了。然后遍历一次数据集，设wordlist长度是m，最后时间复杂度是O(mn²)