【LeetCode】Word Ladder

其实画个图一下就理解了。比如start为hot，end为dog，词典为（hot，dog，dot）
很简单最短的转换是
           hot
            |
           dot
            |
            dog

也就是采用广度优先，从start开始，找出其所有临近词，然后再从找到的临近词开始找它们的临近词语，找到end即停止。这里需要注意的就是，每一个已经找到的词我们都得把它从dict中删去，以免搜寻过程又回走了。比如上图，我们在找寻dot的临近词的时候，就不会找到hot，因为hot已经被处理，我们把它从词典中删掉了。

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int mindepth=0;
        int flag=false;
        vector<string> adj1;
        vector<string> adj2;
        adj2.push_back(start);
        dict.erase(start);

        while(!adj2.empty())
        {
            mindepth++;
            adj1=adj2;
            adj2.clear();
            for(int i=0; i<adj1.size();i++)
            {
                string s=adj1[i];
                for(int i=0;i<s.length();i++)
                {
                    char origchar=s[i];
                    for(char c='a';c<='z';c++)
                    {
                        if(c!=origchar)
                        {
                            s[i]=c;
                            if(s==end) return ++mindepth;
                            if(dict.count(s)) {adj2.push_back(s); dict.erase(s);}
                        }
                    }
                    s[i]=origchar;
                }
            }
        }
        return 0;
    }
};