單詞接龍-LintCode

給出兩個單詞（start和end）和一個字典，找到從start到end的最短轉換序列

比如：

每次隻能改變一個字母。

變換過程中的中間單詞必須在字典中出現。

注意事項

如果沒有轉換序列則傳回0。

所有單詞具有相同的長度。

所有單詞都隻包含小寫字母。

樣例

給出資料如下：

start = “hit”

end = “cog”

dict = [“hot”,”dot”,”dog”,”lot”,”log”]

一個最短的變換序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”，

傳回它的長度 5

#ifndef C120_H
#define C120_H
#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
#include<queue>
#include<map>
using namespace std;
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) {
        // write your code here
        if (start == end)
            return ;
        if (start.size() != end.size())
            return ;
        if (start.empty() || end.empty() || dict.empty())
            return ;
        queue<string> path;
        path.push(start);
        map<string, int> count;
        count[start] = ;
        dict.erase(start);
        while (!path.empty())
        {
            string str = path.front();
            path.pop();
            int n = count[str];
            for (int i = ; i < str.size(); ++i)
            {
                string temp = str;
                for (char j = 'a'; j <= 'z'; ++j)
                {
                    if (temp[i] == j)
                        continue;
                    else
                        temp[i] = j;
                    if (dict.find(temp) != dict.end())
                    {
                        path.push(temp);
                        count[temp] = n + ;
                        dict.erase(temp);
                    }
                    if (temp == end)
                        return n + ;
                }
            }

        }
        return ;
    }
};
#endif