leetcode-Word Ladder II

題目位址：https://leetcode.com/problems/word-ladder-ii/description/

從begin開始的DFS的解法

一開始想到這種解法，送出的時候，對于很長的wordList（測試案例中，長度為95時，肯定會出現TLE），會出現TLE的情況，代碼如下

class Solution {
public:
    vector<bool> visit;
    // 2個字元串之間相等index下，不相等元素的個數
    int dist(string s1, string s2)
    {
        int ret = 0;
        for (int i = 0; i < s1.size(); i++)
            ret += (s1[i] != s2[i]);
        return ret;
    }

    void dfs(string beginWord, string endWord, vector<string>& wordList, 
            vector<vector<string>>& ret, vector<string>& now, int& minLen)
    {
        if (now[now.size() - 1] == endWord)
        // if (dist(now[now.size() - 1], endWord) == 1)
        {
            // 完成一條鍊
            if (now.size() < minLen)
            {
                ret.clear();
                ret.push_back(now);
                minLen = now.size();
            }
            else if (now.size() == minLen)
            {
                ret.push_back(now);
            }
            return;
        }

        for (int i = 0; i < wordList.size(); i++)
        {
            if (!visit[i] && dist(now[now.size() - 1], wordList[i]) == 1 && now.size() + 1 <= minLen)
            {
                visit[i] = true;
                now.push_back(wordList[i]);
                dfs(beginWord, endWord, wordList, ret, now, minLen);
                visit[i] = false;
                now.pop_back();
            }
        }

    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> ret;
        vector<string> now;
        int minLen = wordList.size() + 1;
        if (dist(beginWord, endWord) == 1)
        {
            now.push_back(beginWord);
            now.push_back(endWord);
            ret.push_back(now);
            return ret;
        }
        if (wordList.empty())
            return ret;
        visit.resize( wordList.size() );
        now.push_back( beginWord );
        dfs( beginWord, endWord, wordList, ret, now, minLen);
        return ret;
    }
};

從end開始的BFS

思路：從最後一個字元串開始疊代，一步一步找到最優解，找到最短路徑之後就可以直接退出，這個針對剛才長度為95的字元串清單不存在TLE的問題，但是在長度為4000的字元串列中存在TLE的問題，具體代碼如下

代碼

class Solution {
public:
    vector<vector<bool>> visit;
    // 2個字元串之間相等index下，不相等元素的個數
    int dist(string s1, string s2)
    {
        int ret = 0;
        for (int i = 0; i < s1.size(); i++)
            ret += (s1[i] != s2[i]);
        return ret;
    }

    // 使用dfs，在單詞數組長度很大時，會出現TLE的情況
    void bfs(string beginWord, string endWord, vector<string>& wordList, 
            vector<vector<string>>& ret)
    {
        bool found = false;
        vector<vector<string>> curr;
        vector<vector<bool>> currVisit;
        for (int i = 0; i < ret.size(); i++)
        {
            if (dist(ret[i][ret[i].size() - 1], beginWord) == 1)
            {
                found = true;
                vector<string> tmp( ret[i] );
                tmp.push_back( beginWord );
                curr.push_back( tmp );
            }
        }
        if (found)
        {
            ret = curr;
        }
        // 無法從目前步直接完成
        else
        {
            for (int i = 0; i < ret.size(); i++)
            {
                vector<string> tmp(ret[i]);
                vector<bool> tmpVisit(visit[i]);
                for (int j = 0; j < wordList.size(); j++)
                {
                    if (!visit[i][j] && dist(ret[i][ret[i].size() - 1], wordList[j]) == 1)
                    {
                        found = true;
                        tmp.push_back(wordList[j]);
                        curr.push_back(tmp);
                        tmp.pop_back();

                        tmpVisit[j] = true;
                        currVisit.push_back( tmpVisit );
                        tmpVisit[j] = false;
                    }
                }
            }
            // 找到隻改變了一個字元的字元串
            if (found)
            {
                ret = curr;
                visit = currVisit;
                bfs(beginWord, endWord, wordList, ret);
            }
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> ret;
        vector<string> now;
        vector<bool> tmp( wordList.size() );
        if (wordList.empty())
            return ret;

        bool found = false;
        for (int i = 0; i < wordList.size(); i++)
        {
            if (wordList[i] == endWord)
            {
                found = true;
                tmp[i] = true;
                break;
            }
        }
        if (found)
        {
            now.push_back( endWord );
            ret.push_back( now );
            visit.push_back(tmp);
            bfs( beginWord, endWord, wordList, ret);
        }
        for (int i = 0; i < ret.size(); i++)
        {
            reverse( ret[i].begin(), ret[i].end() );
        }
        if (ret.size() > 0 && ret[0].size() == 1)
            ret.clear();

        return ret;
    }
};

two-end BFS

參考連結：https://leetcode.com/problems/word-ladder-ii/discuss/40540/88ms!-Accepted-c++-solution-with-two-end-BFS.-68ms-for-Word-Ladder-and-88ms-for-Word-Ladder-II

按照上面連結的内容，修改了接口與部分無法通過的case，代碼如下

class Solution126 {
public:
    std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, vector<string>& wordList) {
        std::vector<std::vector<std::string> > paths;
        std::vector<std::string> path(1, beginWord);
        std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end())
            return paths;
        std::unordered_set<std::string> words1, words2;
        words1.insert(beginWord);
        words2.insert(endWord);
        std::unordered_map<std::string, std::vector<std::string> > nexts;
        bool words1IsBegin = false;
        if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
            getPath(beginWord, endWord, nexts, path, paths);
        return paths;
    }
private:
    bool findLaddersHelper(
        std::unordered_set<std::string> &words1,
        std::unordered_set<std::string> &words2,
        std::unordered_set<std::string> &dict,
        std::unordered_map<std::string, std::vector<std::string> > &nexts,
        bool &words1IsBegin) {
        words1IsBegin = !words1IsBegin;
        if (words1.empty())
            return false;
        if (words1.size() > words2.size())
            return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
        for (auto it = words1.begin(); it != words1.end(); ++it)
            dict.erase(*it);
        for (auto it = words2.begin(); it != words2.end(); ++it)
            dict.erase(*it);
        std::unordered_set<std::string> words3;
        bool reach = false;
        for (auto it = words1.begin(); it != words1.end(); ++it) {
            std::string word = *it;
            for (auto ch = word.begin(); ch != word.end(); ++ch) {
                char tmp = *ch;
                for (*ch = 'a'; *ch <= 'z'; ++(*ch))
                    if (*ch != tmp)
                        if (words2.find(word) != words2.end()) {
                            reach = true;
                            words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                        }
                        else if (!reach && dict.find(word) != dict.end()) {
                            words3.insert(word);
                            words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                        }
                        *ch = tmp;
            }
        }
        return reach || findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
    }
    void getPath(
        std::string beginWord,
        std::string &endWord,
        std::unordered_map<std::string, std::vector<std::string> > &nexts,
        std::vector<std::string> &path,
        std::vector<std::vector<std::string> > &paths) {
        if (beginWord == endWord)
            paths.push_back(path);
        else
            for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
                path.push_back(*it);
                getPath(*it, endWord, nexts, path, paths);
                path.pop_back();
            }
    }
};

leetcode-Word Ladder II

leetcode-Word Ladder II

從begin開始的DFS的解法

從end開始的BFS

two-end BFS

繼續閱讀

成員函數初始化清單

LeetCode-110-平衡二叉樹-C語言

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

LeetCode OJ Binary Tree Right Side View

leetcode809

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述