leetcode 127. Word Ladder-蒲公英云

leetcode 127. Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        //vector<vector<string>>re;
        if (beginWord == endWord || beginWord.length() == 1)
            return 2;
        int wl = beginWord.length();
        for (int i = 0; i < wl; i++)
        {
            string s1(beginWord), s2(endWord);
            s1.erase(i, 1); s2.erase(i, 1);
            if (s1 == s2)
                return 2;
        }
        vector<string>words(wordList.begin(), wordList.end());
        map<pair<string,int>, vector<int>>changelist;
        for (int i = 0; i < words.size(); i++)
        {
            for (int j = 0; j < words[0].length(); j++)
            {
                string s = words[i];
                s.erase(j, 1);
                changelist[pair<string, int>(s,j)].push_back(i);
            }
        }
        vector<int>a, b;
        for (int i = 0; i < words.size(); i++)
            a.push_back(i);
        map<string, vector<vector<int>>>head, tail;
        head[beginWord].push_back(b);
        tail[endWord].push_back(b);
        bool flag = true;
        int k = 0;
        while (k < words.size() && flag)
        {
            k++;
            if (tail.size()>head.size())
            {
                map<string, vector<vector<int>>>newhead;
                for (map<string, vector<vector<int>>>::iterator ii = head.begin(); ii != head.end(); ii++)
                {
                    for (int j = 0; j < ii->second.size(); j++)
                    {
                        for (int h = 0; h < wl; h++)
                        {
                            string s = ii->first;
                            s.erase(h, 1);
                            for (int f = 0; f < changelist[pair<string, int>(s,h)].size(); f++)
                            {
                                if (words[changelist[pair<string, int>(s,h)][f]] != ii->first)
                                {
                                    vector<int>::iterator ite = find(ii->second[j].begin(),
                                        ii->second[j].end(), changelist[pair<string, int>(s,h)][f]);
                                    if (ite == ii->second[j].end())
                                    {
                                        map<string, vector<vector<int>>>::iterator nn =
                                            tail.find(words[changelist[pair<string, int>(s,h)][f]]);
                                        if (nn != tail.end())
                                        {
                                            for (int g = 0; g < nn->second.size(); g++)
                                            {
                                                set<int>aa;
                                                set<int>a1(ii->second[j].begin(), ii->second[j].end());
                                                set<int>a2(nn->second[g].begin(), nn->second[g].end());
                                                set_intersection(a1.begin(), a1.end(),
                                                    a2.begin(), a2.end(), inserter(aa, aa.begin()));
                                                if (aa.empty() && (a1.size() > 0 || a2.size() > 0))
                                                    return k + 1;
                                            }
                                        }
                                        if (flag)
                                        {
                                            vector<int>xx = ii->second[j];
                                            xx.push_back(changelist[pair<string, int>(s,h)][f]);
                                            newhead[words[changelist[pair<string, int>(s,h)][f]]].push_back(xx);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                //f = !f;
                head = newhead;
            }
            else
            {
                map<string, vector<vector<int>>>newtail;
                for (map<string, vector<vector<int>>>::iterator ii = tail.begin(); ii != tail.end(); ii++)
                {
                    for (int j = 0; j < ii->second.size(); j++)
                    {
                        for (int h = 0; h < wl; h++)
                        {
                            string s = ii->first;
                            s.erase(h, 1);
                            for (int f = 0; f < changelist[pair<string, int>(s,h)].size(); f++)
                            {
                                if (words[changelist[pair<string, int>(s,h)][f]] != ii->first)
                                {
                                    vector<int>::iterator ite = find(ii->second[j].begin(), ii->second[j].end(), 
                                        changelist[pair<string, int>(s,h)][f]);
                                    if (ite == ii->second[j].end())
                                    {
                                        map<string, vector<vector<int>>>::iterator nn = head.find(words[changelist[pair<string, int>(s, h)][f]]);
                                        if (nn != head.end())
                                        {
                                            for (int g = 0; g < nn->second.size(); g++)
                                            {
                                                set<int>aa;
                                                set<int>a1(ii->second[j].begin(), ii->second[j].end());
                                                set<int>a2(nn->second[g].begin(), nn->second[g].end());
                                                set_intersection(a1.begin(), a1.end(),
                                                    a2.begin(), a2.end(), inserter(aa, aa.begin()));
                                                if (aa.empty() && (a1.size()>0 || a2.size()>0))
                                                    return k + 1;
                                            }
                                        }
                                        if (flag)
                                        {
                                            vector<int>xx = ii->second[j];
                                            xx.push_back(changelist[pair<string, int>(s, h)][f]);
                                            newtail[words[changelist[pair<string, int>(s, h)][f]]].push_back(xx);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                //f = !f;
                tail = newtail;
            }
        }
        return 0;
    }
};