leetcode-Word Ladder

leetcode--Word Ladder

Problem Description:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

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.

分析：根据题目的意思，我首先想到的是利用DFS每次查找到与当前string距离为1的string，用map来标记每次遍历过的string，下次不再比较，然后继续往下搜索，直到找到目标string，记录下距离len，然后与当前最短距离min比较，更新min，最后运行的结果是超时。后来在网上查了一下，才发现是用BFS，而且我的代码中没有充分利用set查找时间复杂度是O(1)的特性，每次都遍历map比较的时间复杂度达到O(mn)，其中m是字符串长度，n是set的元素个数。原始代码记录一下：

class Solution {
public:
    
    bool distance(string a,string b)
    {
        int dist=0;
        for(int i=0;i<a.size();++i)
        {
            if(a[i]!=b[i])
            dist++;
        }
        if(dist==1)
            return true;
        else
            return false;
    }
    
    bool dfs(string start,string end,map<string,bool> &flag,int &res,int &min)
    {
        if(start==end)
        {
            if(res<min)
                min=res;
            return true;
        }
        
        for(map<string,bool>::iterator i=flag.begin();i!=flag.end();++i)
        {
            if((*i).second==true&&distance(start,(*i).first))
            {
                res++;
                (*i).second=false;
                dfs((*i).first,end,flag,res,min);
                (*i).second=true;
                res--;
            }
        }
        return false;
    }
    
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        int res=0;
        int len=dict.size();
        if(len==0||start==end)
            return 0;
        int min=dict.size()+1;
        map<string,bool> flag;
        for(unordered_set<string>::iterator iter=dict.begin();iter!=dict.end();++iter)
            flag.insert(make_pair(*iter,true));
        bool tag=false;
        tag=dfs(start,end,flag,res,min);
        if(tag)
            return min+1;
        else
            return 0;
        
        
    }
};

Submission Result: Time Limit Exceeded

利用BFS遍历的代码如下：

class Solution {
public:
    
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        int res=0;
        if(start==end||dict.size()==0)
            return res;
        unordered_set<string> midstr;//记录层次遍历的string，防止循环搜索
        queue<string> strque;
        strque.push(start);
        int lev=1,count=0; //用于记录队列每层的元素个数
        while(!strque.empty())
        {
            lev--;
            string str=strque.front();
            strque.pop();
            if(str==end)
            {
                res++;
                break;
            }
            
            midstr.insert(str);
            for(int i=0;i<str.size();++i)
                for(char ch='a';ch<='z';++ch)
                {
                    string temp=str;
                    if(str[i]==ch)
                        continue;
                    temp[i]=ch;
                        
                    if(dict.count(temp)==1&&midstr.count(temp)==0)
                    {
                        
                        count++;
                        strque.push(temp);
                        midstr.insert(temp);
                    }
                }
            if(lev==0)//当前层遍历完毕
            {
                res++;
                lev=count;
                count=0;
            }
        }
 
        if(res==1)//如果是1说明不存在路径，按照题目的设置，没有路径为1的情况
            return 0;
        else
            return res;
    }
};

Submission Result: Time Limit Exceeded

相关推荐