Leetcode 127. 单词接龙（DAY 169）---- LeetCode 精选 TOP 面试题

爱被打了一巴掌 2022-09-11 05:17 123阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷超时 Dijkstra算法）
     *  代码实现（首刷自解 C++ 600ms）
     *  代码实现（首刷优化 vector改queue 256ms）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷超时 Dijkstra算法） ##

--------------------

class Solution { 
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) { 
            wordList.emplace_back(beginWord);
            auto pos = find(wordList.begin(),wordList.end(),endWord);
            if(pos == wordList.end())   return 0;
            int startpos = pos-wordList.begin(),endpos = (--wordList.end()) - wordList.begin(),maxlength = 10000;
            
            vector<vector<int>> cnt(wordList.size(),vector<int>(wordList.size(),maxlength));
            vector<int> v(wordList.size(),maxlength);
            vector<bool> visit(wordList.size(),false);
            visit[endpos] = visit[startpos] = true;
    
            for(int i=0;i<wordList.size();++i)
            { 
                for(int j=0;j<wordList.size();++j)
                { 
                    int tmp = 0;
                    if(i > j) cnt[i][j] = cnt[j][i];
                    else if(i == j) cnt[i][j] = 0;
                    else
                    { 
                        for(int k=0;k<wordList[i].size();++k)
                        { 
                            if(wordList[i][k] != wordList[j][k])
                                ++tmp;
                            if(tmp > 1) break;
                        }
                        if(tmp == 1) cnt[i][j] = tmp;
                    } 
                }
            }
    
            for(int i=0;i<wordList.size();++i)
                v[i] = cnt[startpos][i];
    
            while(1)
            { 
                int tmp = -1,next = -1;
                for(int i=0;i<visit.size();++i)
                { 
                    if(!visit[i] && (tmp == -1 || v[i] < maxlength && v[i] < tmp))
                    { 
                        tmp = v[i];
                        next = i;
                    }
                }
    
                if(next == -1)  break;
    
                visit[next] = true;
                for(int i=0;i<visit.size();++i)
                { 
                    if(cnt[next][i] < maxlength)
                    { 
                        cnt[startpos][i] = min(v[next] + cnt[next][i],cnt[startpos][i]);
                        v[i] = cnt[startpos][i];
                    }
                }
            }
    
            return v[endpos] < maxlength ? v[endpos]+1 : 0;
        }
    };

--------------------

## 代码实现（首刷自解 C++ 600ms） ##

--------------------

class Solution { 
    public:
        bool handler(string& str1,string& str2)
        { 
            int diffcnt = 0;
            for(int i=0;i<str1.size();++i)
            { 
                if(str1[i] != str2[i])  ++diffcnt;
                if(diffcnt > 1) return false;
            }
            return diffcnt == 1;
        }
    
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) { 
            wordList.emplace_back(beginWord);
            auto pos = find(wordList.begin(),wordList.end(),endWord);
            if(pos == wordList.end())   return 0;
    
            vector<string> now,next;
            vector<bool> visit(wordList.size(),false);
            visit[pos-wordList.begin()] = true;
            now.emplace_back(endWord);
            int ret = 0;
    
            while(now.size())
            { 
                ++ret;
                for(auto& str:now)
                { 
                    for(int i=0;i<visit.size();++i)
                    { 
                        if(visit[i] || !handler(str,wordList[i]))    continue;
                        if(wordList[i] == beginWord)    return ++ret;
                        next.emplace_back(wordList[i]);
                        visit[i] = true;
                    }
                }
                now = next;
                next.clear();
            }
    
            return 0;
        }
    };
        }
    };

--------------------

## 代码实现（首刷优化 vector改queue 256ms） ##

--------------------

class Solution { 
    public:
        bool handler(string& str1,string& str2)
        { 
            int diffcnt = 0;
            for(int i=0;i<str1.size();++i)
            { 
                if(str1[i] != str2[i])  ++diffcnt;
                if(diffcnt > 1) return false;
            }
            return diffcnt == 1;
        }
    
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) { 
            wordList.emplace_back(beginWord);
            auto pos = find(wordList.begin(),wordList.end(),endWord);
            if(pos == wordList.end())   return 0;
    
            queue<string> q;
            q.emplace(endWord);
            int ret = 0;
    
            while(q.size())
            { 
                ++ret;
                int size = q.size();
                while(size--)
                { 
                    auto str = q.front();
                    q.pop();
                    for(auto& s:wordList)
                    { 
                        if(s.empty() || !handler(str,s))    continue;
                        if(s == beginWord)    return ++ret;
                        q.emplace(s);
                        s.clear();
                    }
                }
            }
    
            return 0;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0a6a354d54314ad08c77d8fd9cbb217e.png