127. 单词接龙

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
       
        map<int, map<string, vector<string>>> tree;

        for (int i = 0; i < wordList.size(); i++)
        {
            for (int j = 0; j < wordList[i].size(); j++)
            {
                string s = wordList[i];
                s.erase(j, 1);
                map<string, vector<string>> & m = tree[j];
                m[s].push_back(wordList[i]);
            }
        }

        list<pair<string, int>> queue;
        queue.push_back(make_pair(beginWord,1 ));

        set<string> tmp;

        while (true)
        {
            if (queue.empty())
                return 0;

            string s = queue.front().first;
            int curstep = queue.front().second;

            queue.pop_front();

            for (int i = 0; i < s.size(); i++)
            {
                string ss = s;
                ss.erase(i, 1);

                map<string, vector<string>> & tt = tree[i];

                if (tt.find(ss) != tt.end())
                {
                    vector<string> & vt = tt[ss];

                    for (int j = 0; j < vt.size(); j++)
                    {
                        if (vt[j] == endWord)
                        {
                            return curstep + 1;
                        }

                        if (tmp.find(vt[j]) == tmp.end())
                        {
                            queue.push_back(make_pair(vt[j], curstep + 1));
                            tmp.insert(s);
                        }
                    }
                }
            }
        }

        return 0;
    }
};