lintcode-单词接龙I

给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列
比如：
每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。

注意事项
如果没有转换序列则返回0。
所有单词具有相同的长度。
所有单词都只包含小写字母。

您在真实的面试中是否遇到过这个题？ Yes

样例给出数据如下：

start = "hit" end = "cog"

dict = ["hot","dot","dog","lot","log"]

一个最短的变换序列是
"hit" -> "hot" -> "dot" ->"dog" -> "cog"，

返回它的长度 5

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    int ladderLength(string start, string end, unordered_set<string> &dict) {    
          
        vector<vector<string>> result;
        if(start.size() == 0 || end.size() == 0 || dict.size() == 0) {
            return 0;
        }
        
        //start 和 end 都为‘a’, dict 为‘b’ 答案是1？？？？？
        if(start.size() == end.size() && start.size() == 1) {
            return 1;
        }
        
        map<string, int> count; //到某个字符串时，序列的长度
        queue<string> qu;
        qu.push(start);
        dict.erase(start);
        count[start] = 1;
        
        int minLen = 0x7fffffff;
        vector<string> curList;
        
        while(!qu.empty() && dict.size() >= 0) {
            string curString = qu.front();
            qu.pop();
            int curLen = count[curString];
            for(int i = 0; i < curString.size(); ++i) {
                string tmp = curString;
                for(char j = 'a'; j <= 'z'; ++j) {
                    if(tmp[i] == j) {
                        continue;
                    } else {
                        tmp[i] = j;
                        
                        if(dict.find(tmp) != dict.end()) {
                            //cout << tmp << endl;
                            qu.push(tmp);
                            count[tmp] = curLen + 1;
                            dict.erase(tmp);
                            if(tmp == end) {
                                return count[tmp]; //end可能包含在dict中
                            }
                        } else if(tmp == end) {
                            //cout << tmp << endl;
                            count[tmp] = count[curString] + 1;
                            return count[tmp];
                        }
                    }
                }
            }
        } 
        
        return 0;
    } 
};