程序员面试金典 - 面试题 17.22. 单词转换（BFS）

示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
["hit","hot","dot","lot","log","cog"]

示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

class Solution {
public:
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> ans, frontPath, newpath;
        int len = wordList.size(), i, k, n, lv = 0;
        unordered_map<string,int> m;
        vector<bool> visited(len,false);
        for(i = 0; i < len; ++i)
        {
            m[wordList[i]] = i;
            if(wordList[i] == beginWord)
                visited[i] = true;
        }
        if(m.find(endWord) == m.end())
        	return {};
        queue<vector<string>> q;
        frontPath.push_back(beginWord);
        q.push(frontPath);
        string str;
        while(!q.empty())
        {
        	lv++;
        	n = q.size();
        	while(n--)
        	{
                frontPath = q.front();
                q.pop();
	        	for(i = 0; i < beginWord.size(); ++i)
	        	{//对每个单词的每个字符进行改变
                    str = frontPath.back();
                    for(k = 1; k <= 25; ++k)
                    {
    	        		str[i] += 1;
    	        		if(str[i] > 'z')
    	        			str[i] = 'a';
    	        		if(m.find(str) != m.end() && !visited[m[str]])
    	        		{	//在集合中，且没有访问的
                            newpath = frontPath;
    	        			newpath.push_back(str);
                            q.push(newpath);
    	        			visited[m[str]] = true;
    	        			if(str == endWord)
            					return newpath;
    	        		}
                    }
	        	}
	        }
        }
        return {};
    }
};