字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

Solution

Hard

参考 liuyubobobo 的解题思路

• 广度优先搜索
• 时间复杂度 O(n^2^)，空间复杂度 O(n)

// @lc code=start
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int end = find(wordList.begin(),wordList.end(), endWord)-wordList.begin();
        if(end == wordList.size()) return 0;

        int begin = find(wordList.begin(),wordList.end(),beginWord) - wordList.begin();
        if(begin == wordList.size()) 
            wordList.push_back(beginWord);

        int n = wordList.size();
        vector<vector<bool>> g(n, vector<bool>(n, false));
        for(int i=0; i<n; ++i){
            for(int j=0; j<i; ++j)
                g[i][j] = g[j][i] = similar(wordList[i], wordList[j]);
        }

        // BFS
        queue<int> q;
        vector<int> step(n, 0);
        q.push(begin);
        step[begin] = 1;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int i=0; i<n; ++i){
                if(step[i]==0 && g[cur][i]){
                    if(i==end)
                        return step[cur]+1;
                    step[i] = step[cur] + 1;
                    q.push(i);
                }
            }
        }
        return 0;
    }
private:
    bool similar(const string& word1, const string& word2){
        int diff = 0;
        for(int i=0; i<word1.size(); ++i){
            if(word1[i] != word2[i]){
                diff += 1;
                if(diff>1)
                    return false;
            }
        }
        return true;
    }
};
// @lc code=end

参考 @liweiwei1419 、**@Drinkwater** 的题解

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if ( words.empty() || words.find(endWord) == words.end() ) return 0;
        words.erase(beginWord);
        queue<string> que;
        que.push(beginWord);
        unordered_set<string> visited;
        visited.insert(beginWord);
        int step = 1;
        while ( !que.empty() ) {
            // 找到没有被访问过, 而且能够由当前单词转换而成的单词
            int n = que.size();
            // 每一轮(每一层step加个1)
            while ( n-- ) {
                string curWord = que.front();
                que.pop();
                // 当前单词的每个字符都替换成其他的25个字符, 然后在单词表中查询
                // 是不是包含转换后的单词
                // 这里千万不能遍历单词表, 因为单词表很长, 而哈希表使用的红黑树
                // 的查询效率比遍历单词表高很多
                for ( int i = 0; i < curWord.size(); ++i ) {
                    char originalChar = curWord[i];
                    for ( int j = 0; j < 26; ++j ) {
                        if ( char('a' + j) == originalChar ) continue;
                        curWord[i] = (char)('a' + j);
                        if ( words.find(curWord) != words.end() && visited.find(curWord) == visited.end() ) {
                            if ( curWord == endWord ) return step + 1;
                            else {
                                que.push(curWord);
                                visited.insert(curWord);
                            }
                        }
                    }
                    curWord[i] = originalChar;
                }
            }
            ++step;
        }
        return 0;
    }
};