题目描述

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:

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.

算法1

(BFS) $O(len)$

替换beginWord的每个字符，符合条件的放入queue，并记录当前的路径步数，一旦找到endWord，路径为最短。

时间复杂度

遍历每个字符，len为beginWord长度。O（len）
需要queue存储candidate，O（n），n为dict数组长度。需要hashmap来记录每个candidate的路径步数，O（n）。

参考文献

C++ 代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if(!dict.count(endWord)) return 0;
        unordered_map<string, int> m;
        m[beginWord]=1;
        q.push(beginWord);

        while(!q.empty())
        {
            auto t=q.front(); q.pop();
            if(t==endWord) return m[endWord];
            string word=t;
            for(auto &c:word)
            {
                for(int i=0;i<26;i++)
                {
                    c='a'+i;
                    if(word!=t && dict.count(word) && !m.count(word))
                    {
                        m[word]=m[t]+1;
                        q.push(word);
                    }
                }
                word=t;
            }
        }
        return 0;
    }
};