Leetcode127: 单词接龙

【题目描述】
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

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

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。

【思路分析】
BFS

1. 初始化将beginWord加入到queue中，然后一次性pop出queue中所有的单词，将其相邻的单词加入queue中
2. 如何找到相邻单词 - 暴力枚举 对于单词的每一位，将它换为'a'-'z'。如果变更后的单词在wordSet中，则将其加入queue。 是target则返回。不是wordSet则pass。
3. 由于求最短路径，一个word只能用一次， 所以每次把单词加入Queue的时候把该单词从Queue中删掉

【坑】

1. 注意题意，这里返回的是链表的长度，不是需要改变的步骤
2. 对一个单词修改循环后，要记得还原回原来的 --- 开始修改遍历前用变量保存本来这个位置的字母

代码

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    // create wordlist set
    unordered_set<string> wordSet;
    for (int i = 0; i < wordList.size(); ++i) {
        wordSet.insert(wordList[i]);
    }

    queue<string> q;
    int step = 0;

    if (!wordSet.count(endWord)) return 0;
    if (wordSet.count(beginWord)) {
        wordSet.erase(beginWord);
    }

    q.push(beginWord);
    while (!q.empty()) {
        step++;
        int size = q.size();
        while (size > 0) {
            string cur = q.front();
            q.pop();
            size--;
            for (int i = 0; i < cur.size(); i++) {
                char c = cur[i];
                for (char z = 'a'; z <= 'z'; z++) {
                    cur[i] = z;
                    if (cur == endWord) return step + 1;
                    else if (wordSet.count(cur)) {
                        wordSet.erase(cur);
                        //cout << "step: " << step << endl;
                        //cout << cur << endl;
                        //cout << "-----------" << endl;
                        q.push(cur);
                    }
                }
                //back the start state 
                cur[i] = c;   
            }
        }

    }
    return 0;
}