Word Ladder

code

#include <list>
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(dict.size() == 0)
        {
            return 0;
        }

        if(start == end)
        {
            return 1;
        }

        list<string> queue;
        int level = 1;
        unordered_set<string> hash;
        hash.insert(start);
        queue.push_back(start);
        dict.insert(end);

        while(!queue.empty())
        {
            level++;
            int size = queue.size();
            for(int z = 0; z < size; z++)
            {
                string now = queue.front();
                queue.pop_front();
                //cout<<now<<endl;

                for(string s : getWords(now, dict))
                {
                    if(hash.find(s) != hash.end())
                    {
                        continue;
                    }
                    //cout<<level<<" "<<s<<endl;
                    if(s == end)
                    {
                        return level;
                    }

                    queue.push_back(s);
                    hash.insert(s);
                }
            }

        }

        return 0;

    }

    vector<string> getWords(string s, unordered_set<string> &dict)
    {
        vector<string> ret;
        for(int i = 0; i<s.length(); i++)
        {
            string shadow = s;
            for(int j = 0; j<26; j++)
            {
                shadow[i] = 'a' + j;
                if(dict.find(shadow) != dict.end())
                {
                    ret.push_back(shadow);
                }
            }
        }
        return ret;
    }
};