leetcode 127. Word Ladder

曾经终败给现在 2022-07-26 01:41 136阅读 0赞

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

1.  Only one letter can be changed at a time
2.  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;
    	}
    };

accepted