LeetCode: 126. Word Ladder II

LeetCode: 126. Word Ladder II

最近工作和毕设压力比较大, 刷 LeetCode 有点不在状态,代码可能有点难看。不过,整体的思路应该是没有问题的。

题目描述

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

题目大意: 根据给定的开始结束单词以及字母表,找到所有从开始单词到结束单词的最短路径。要求路径上的每个单词之间只有一个字母之差。

解题思路 —— 广度搜索

广度搜索可以直接求到最短路径。我们可以在计算最短路径的过程中,记录下当前到达节点的最短路径的前驱,然后推出所有的路径。如下图:

虽然 dot <--> lot, dog <--> log 等路径也存在,但其不是到达相应节点的最短路径,因此可以忽略掉。如下图:

AC 代码

class Solution {
private:
    // 记录广度搜索状态的结构
    struct LadderState
    {
        vector<string> frontState;  // 记录当前状态是由哪些状态转换而来
        int level;                  // 记录当前状态的层数
    };
private:
    // 判断两个单词是否只相差一个字母
    bool isNear(string lhv, string rhv)
    {
        if(lhv.size() != rhv.size()) return false;

        int cnt = 0;
        for(int i = 0; i < lhv.size() && cnt < 2; ++i)
        {
            if(lhv[i] != rhv[i])
            {
                ++cnt;
            }
        }

        return (cnt == 1);
    }    
    // 返回到达 endWord 的所有最短路径
    set<vector<string>> recoverPaths(string beginWord, string endWord, map<string, LadderState>& wordStates)
    {
        if(beginWord == endWord) return {{beginWord}};
        set<vector<string>> paths;
        for(size_t i = 0; i < wordStates[endWord].frontState.size(); ++i)
        {
            set<vector<string>> curPaths = recoverPaths(beginWord, wordStates[endWord].frontState[i], wordStates);
            for(auto path : curPaths)
            {
                path.push_back(endWord);
                paths.insert(path);
            }
        }

        return paths;
    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        multimap<string, string> wordDir; //wordDir[i] = j 表示 i 到 j 只有一个字母不同

        // 计算距离,将相邻的节点存入 wordDir 中
        for(int i = 0; i < wordList.size(); ++i)
        {
            for(int j = i+1; j < wordList.size(); ++j)
            {
                if(isNear(wordList[i], wordList[j]))
                {
                    wordDir.insert({wordList[i], wordList[j]});
                    wordDir.insert({wordList[j], wordList[i]});
                }
            }
        }
        for(int i = 0; i < wordList.size(); ++i)
        {
            if(isNear(wordList[i], beginWord))
            {
                wordDir.insert({wordList[i], beginWord});
                wordDir.insert({beginWord, wordList[i]});
            }
        }

        // 初始化各个节点的状态
        map<string, LadderState> wordStates;
        for(size_t i = 0; i < wordList.size(); ++i)
        {
            wordStates[wordList[i]] = { {}, 0};
        }
        wordStates[beginWord] = { {}, 0 };

        // 计算最短路径
        queue<string> que;
        unordered_set<string> flags;

        que.push(beginWord);
        que.push("#");
        flags.insert(beginWord);
        int stepNum = 0;

        while(!que.empty())
        {
            string curWord = que.front();
            que.pop();

            if(curWord == "#") 
            {
                ++stepNum;
                if(!que.empty()) que.push("#");
                continue;
            }

            if(curWord == endWord)
            {
                continue;
            }

            for(auto iter = wordDir.find(curWord); iter != wordDir.end() && iter->first == curWord; ++iter)
            {
                if(flags.find(iter->second) == flags.end())
                {
                    flags.insert(iter->second);
                    que.push(iter->second);
                    wordStates[iter->second].level = wordStates[curWord].level + 1;
                }

                if(wordStates[iter->second].level == wordStates[curWord].level + 1)
                {
                    wordStates[iter->second].frontState.push_back(curWord);
                }
            }
        }

        // 根据 wordStates 恢复各个路径
        set<vector<string>> paths = recoverPaths(beginWord, endWord, wordStates);
        vector<vector<string>> ans(paths.begin(), paths.end());
        return ans;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:10
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务