Leetcode.127 单词接龙

题目链接

Leetcode.127 单词接龙

题目描述

字典 wordList中从单词 beginWord和 endWord的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

• 每一对相邻的单词只差一个字母。
• 对于 $1<=i<=k$ 时每个 $s_i$ 都在 wordList中。注意 beginWord不需要在 wordList中。
• $s_k==endWord$
  给你两个单词 beginWord和 endWord和一个字典 wordList返回 从 beginWord到 endWord的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。

示例 1

输入beginWord = “hit”, endWord = “cog”, wordList =[“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出5
解释一个最短转换序列是 “hit” -> “hot”-> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2

输入beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出0
解释endWord “cog” 不在字典中所以无法进行转换。

提示

• $1<=beginWord.length<=10$
• $endWord.length==beginWord.length$
• $1<=wordList.length<=5000$
• $wordList[i].length==beginWord.length$
• beginWord、endWord和 wordList[i]由小写英文字母组成
• $beginWord!=endWord$
• wordList中的所有字符串 互不相同

分析

由于是求 最短序列所以可以使用BFSBFS 可以求最短路。

先用一个哈希表记录单词表中的所有单词。

用一个队列 q 先将beginWord入队然后开始BFS并用一个 ans 记录最短序列长度。如果中途能够达到 endWord就返回最短序列长度否则返回 0。

时间复杂度$O(26m\ast n^2)$

代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //用一个哈希表记录所有的单词
        unordered_set<string> uset;
        for(auto &s:wordList) uset.insert(s);

        //如果结尾单词 不在哈希表里 说明beginword 无法转换为 endword 返回0
        if(!uset.count(endWord)) return 0;

        //队列 进行bfs
        queue<string> q;
        q.push(beginWord);

        //记录最短序列长度
        int ans = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i = 0;i < sz;i++){
                //队列首部元素出队
                auto s = q.front();
                q.pop();
                //如果是endword 说明已经达到了终点 直接返回
                if(s == endWord) return ans + 1;
                
                //查找uset中 是否还有能被此时的 s 转换为的单词
                //s 的每一位字符都要枚举 因为转换规则是 只有一个字符不同 其他都相同的字符串
                int n = s.size();
                for(int i = 0;i < n;i++){
                //记录原始位置的字符 操作结束之后要变回去
                    char op = s[i];
                    for(char c = 'a';c <= 'z';c++){
                        //与 原字符op 相同就跳过 否则才修改进行查找
                        if(op == c) continue;
                        s[i] = c;
                        //如果 uset中有这样的字符 说明原字符串 s 可以转换为 新的字符串 s'                  
                        //就将此时的 s' 入队并且uset删除此时的 s'
                        if(uset.count(s)){
                             q.push(s);
                             uset.erase(s);
                        }
                    }
                    //恢复现场
                    s[i] = op;
                } 
            }
            ans++;
        }
        return 0;
    }
};