leetcode：127. 单词接龙

题目

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

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例：

  1. 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
  2. 输出：5
  3. 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
  1. 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
  2. 输出：0
  3. 解释：endWord "cog" 不在字典中，所以无法进行转换。

解答 & 代码

层序遍历

  1. class Solution {
  2. public:
  3.     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
  4.         // 将所有单词存储到哈希表，以便能在 O(1) 时间复杂度内判断一个单词是否存在 wordList 中
  5.         unordered_set<string> wordsDict(wordList.begin(), wordList.end());
  6.         // 如果 endWord 不在 wordList，肯定不存在转换序列，直接返回 0
  7.         if(wordsDict.find(endWord) == wordsDict.end())
  8.             return 0;
  10.         queue<string> wordQ;            // 队列，存储层序遍历的节点（单词）
  11.         wordQ.push(beginWord);
  12.         unordered_set<string> visited;    // 哈希表，存储已访问过的单词
  13.         visited.insert(beginWord);
  14.         int depth = 1;                    // 当前序列的单词数
  15.         // 层序遍历
  16.         while(!wordQ.empty())
  17.         {
  18.             int levelCnt = wordQ.size();
  19.             for(int i = 0; i < levelCnt; ++i)
  20.             {
  21.                 string curWord = wordQ.front();
  22.                 wordQ.pop();
  23.                 // 对于当前单词的每一位，依次改为 26 个字母
  24.                 for(int j = 0; j < curWord.size(); ++j)
  25.                 {
  26.                     char originCh = curWord[j];
  27.                     for(int k = 0; k < 26; ++k)
  28.                     {
  29.                         curWord[j] = 'a' + k;
  30.                         // 如果修改后的单词没被访问过，且存在 wordList 中，则存入队列（相当于当前单词的孩子节点）
  31.                         if(visited.find(curWord) == visited.end() &&
  32.                             wordsDict.find(curWord) != wordsDict.end())
  33.                         {
  34.                             // 如果修改后的单词就是 endWord，直接返回
  35.                             if(curWord == endWord)
  36.                                 return depth + 1;
  37.                             else
  38.                             {
  39.                                 wordQ.push(curWord);
  40.                                 visited.insert(curWord);
  41.                             }
  42.                         }
  43.                     }
  44.                     curWord[j] = originCh;    // 撤销对当前位的修改，去修改下一位字符
  45.                 }
  46.             }
  47.             ++depth;
  48.         }
  49.         return 0;
  50.     }
  51. };

复杂度分析：设字典 wordList 中包含 n 个单词，设单词长度 m

  • 时间复杂度 O(nm26)：访问每个单词一次，对于每个单词，遍历其每一位，分别修改为 26 个字母，看修改后的字符是否存在字典中且未被访问过
  • 空间复杂度 O(nm)：
    • 哈希表 wordsDict 存储所有单词，每个单词长为 m
    • 队列 wordQ 存储 BFS 遍历的节点（单词），存储的单数 O(n)，每个单词长为 m
    • 哈希表 visited 存储访问过的单词，最多 n 个，每个单词长为 m

执行结果：

  1. 执行结果：通过
  3. 执行用时：164 ms, 在所有 C++ 提交中击败了 39.14% 的用户
  4. 内存消耗：14.8 MB, 在所有 C++ 提交中击败了 61.99% 的用户