leetcode—word ladder II

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

1 problem description

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
 
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
 
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
 
Return
 
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

2 ideas

I see this topic was similar to the minimum spanning tree, should be to do with greedy algorithm, greedy algorithm ideas are as follows:

       From the start string starting, find a transform can obtain a string string set S1, if the set S1 contains end string, then the search is over, otherwise, the search can be two steps to arrive on the same set of S2, to judge whether a string sets within two steps to the end string, and so on, eventually to find the shortest path. In addition, the path to save the need to separate a data structure,

The final algorithm described below (class of minimum spanning tree):

  1. All string dictionary in dict is divided into left and right sides, one side is the leftside=start (the actual code without storage), one side is the rightside= (dict-start), the start from the farthest node, such as curStep = start from the node of up to start I step within the set (for the initial 0 step up).
  2. Calculation of nextStep, It is the string i+1 step reachable set, The most simple way is the following ideas, CurStep rightside traversal traversal, By comparison, Must be able to find the nextStep, Find the nextStep curStep into nextStep, erase the strings in nextStep from rightside., NextStep emptied continue to search until nextStep or rightside is empty (no path to end), Or end was found.

Therefore the following this code:

class Solution {
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        // end typing your C/C++ solution below
        // DO NOT write int main() function
        //
 
        map<string,vector<string> > path;
 
        unordered_set<string>leftside;
        unordered_set<string>rightside=dict;
        rightside.insert(start);
        rightside.insert(end);
 
        leftside.insert(start);
        rightside.erase(start);
 
        unordered_set<string>curStep;
        unordered_set<string>nextStep;
        curStep.insert(start);
        while(curStep.find(end)==curStep.end()&&!rightside.empty())
        {
            
            unordered_set<string>::iterator iter_us_cur;
            unordered_set<string>::iterator iter_us_right;
 
            for(iter_us_cur=curStep.begin();iter_us_cur!=curStep.end();++iter_us_cur)
            {
                
 
                for(iter_us_right=rightside.begin();iter_us_right!=rightside.end();++iter_us_right)
                {
                    
                    if(isCvtable(*iter_us_cur,*iter_us_right))
                    {
                        if(path.find(*iter_us_cur)!=path.end())
                        {
                            path[*iter_us_cur].push_back(*iter_us_right);
                        }
                        else
                        {
                            vector<string> emptyV;
                            path[*iter_us_cur]=emptyV;
                            path[*iter_us_cur].push_back(*iter_us_right);
                        }
 
                        nextStep.insert(*iter_us_right);
                    }
                }
 
            }
 
            if(nextStep.empty())break;
            for(iter_us_right=nextStep.begin();iter_us_right!=nextStep.end();++iter_us_right)
            {
                rightside.erase(*iter_us_right);
            }
            curStep = nextStep;
            nextStep.clear();
        }
 
        vector<vector<string> > result;
        vector<string> temp;
 
        if(curStep.find(end)!=curStep.end())
        {
            output(path,start,end,result,temp);
        }
 
        return result;
 
    }
    bool isCvtable(string str1,string str2)
    {
        //cout<<"isCvtable: "<<str1<<str2<<endl;
        if(str1.length()!=str2.length()){return false;}
        
        int count=0;
        for(int i = 0;i<str1.length();++i)
        {
            if(str1[i]!=str2[i])count++;
            if(count>1)return false;
        }
        
        return count==1;
    }
 
 
    void output(map<string,vector<string> >&path,string start,string end,vector<vector<string> >&result,vector<string> & temp)
    {
        temp.push_back(start);
 
        if(start==end)
        {
            result.push_back(temp);return;
        }
 
        vector<string>::iterator iter_v;
        
        for(iter_v=path[start].begin();iter_v!=path[start].end();++iter_v)
        {
            output(path,*iter_v,end,result,temp);temp.pop_back();
        }
    }
};

 

After submitting the online judge, a small data set is no problem, but the large data sets of TLE, analyzed the process, is mainly for nextStep from curStep is too time-consuming, I this is O (N2) time complexity, the results are as follows:

image

This case got about 3000 words, large, analysis, parameter to the topic of unordered_set is a purpose, unordered_set actual bottom is a hash table, so can a string constant time index, based on this idea, in the known curStep, rightside and nextStep.:

        For each string in curStep, assuming the length is M, then its each have 25 changes, namely each word with the changes in 25*M, then the time complexity into O (MN), the word length is generally not too high, so this is a linear algorithm, analysis is completed, I started writing algorithm:

class Solution {
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        // end typing your C/C++ solution below
        // DO NOT write int main() function
        //
 
        map<string,vector<string> > path;
 
        unordered_set<string>rightside=dict;
 
        rightside.erase(start);
        
        unordered_set<string>curStep;
        unordered_set<string>nextStep;
        curStep.insert(start);
        while(curStep.find(end)==curStep.end()&&!rightside.empty())
        {
            unordered_set<string>::iterator iter_us_cur;
            for(iter_us_cur=curStep.begin();iter_us_cur!=curStep.end();++iter_us_cur)
            {
                string temp;
                for(int i=0;i<(*iter_us_cur).length();++i)
                {
                    for(int j = 0;j<26;j++)
                    {
                        temp = *iter_us_cur;
                        if(temp[i]!=('a'+j))
                        {
                            temp[i] = ('a'+j);
                        }
                        
                        if(rightside.count(temp)==1)
                        {
                            nextStep.insert(temp);
                            if(path.find(*iter_us_cur)==path.end())
                            {
                                vector<string> emptyV;
                                path.insert(make_pair(*iter_us_cur,emptyV));
                            }
                            
                            path[*iter_us_cur].push_back(temp);
                        }
                    }                    
                }
            }
            
            if(nextStep.empty())break;
            unordered_set<string>::iterator iter_set;
            for(iter_set=nextStep.begin();iter_set!=nextStep.end();++iter_set)
            {
                rightside.erase(*iter_set);
            }
            curStep = nextStep;
            nextStep.clear();
        }
        
        vector<vector<string> > result;
        vector<string> temp;
        
        if(curStep.find(end)!=curStep.end())
        {
            output(path,start,end,result,temp);
        }
 
        return result;
 
    }
    
    void output(map<string,vector<string> >&path,string start,string end,vector<vector<string> >&result,vector<string> & temp)
    {
        temp.push_back(start);
 
        if(start==end)
        {
            result.push_back(temp);return;
        }
 
        vector<string>::iterator iter_v;
        
        for(iter_v=path[start].begin();iter_v!=path[start].end();++iter_v)
        {
            output(path,*iter_v,end,result,temp);temp.pop_back();
        }
    }
};

 

Results out of the wonderful moment:

image

In addition, the output means there is also room for improvement, as shown in the diagram, the program path is such a picture, actually an adjacency list.

image

Our algorithm is depth first search starting from start, until end, when the search to the last node end is not actually invalid search (and large proportion), so can put the picture in turn, and then starting from end reverse search, using space for time.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Stacey at November 16, 2013 - 4:05 PM