LeetCode127题：单词接龙

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  

• 导航：

  • LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
  • 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
  • python源码解读：解读python的源代码与调用关系，快速提升代码质量
  • python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
  • 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

题目描述

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次只能改变一个字母。
2. 转换过程中的中间单词必须在字典 wordList 中。

说明：

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只包含小写字母。
• 字典 wordList 是非空的，且不包含重复的单词。
• beginWord 和 endWord 是非空的，且不相同。

示例 1:

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

输出: 5

解释: 最短转换序列为 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。
1
2
3
4
5
6
7
8
9

示例 2:

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

输出: 0

解释: endWord "cog" 不在字典 wordList 中，因此无转换可能。
1
2
3
4
5
6
7
8

方法一：广度优先搜索（BFS）

解题步骤

1. 将 wordList 转换为集合 wordSet，以便快速查找。
2. 使用队列实现广度优先搜索。队列中的每个元素是一个元组，包括当前单词和到达该单词的转换次数。
3. 对于队列中的每个单词，生成所有可能的单词变换，并检查是否在 wordSet 中。如果在，加入队列继续搜索。
4. 如果找到 endWord，则当前转换次数即为答案。
5. 如果队列耗尽还没有找到 endWord，则表示无法从 beginWord 转换到 endWord。

Python 示例

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)  # 快速查找
    if endWord not in wordSet:
        return 0
    queue = deque([(beginWord, 1)])  # (当前单词, 步数)
    
    while queue:
        current_word, level = queue.popleft()
        if current_word == endWord:
            return level
        
        # 生成所有单个字符变换的可能单词
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + c + current_word[i+1:]
                if next_word in wordSet:
                    wordSet.remove(next_word)  # 移除已访问过的单词防止循环访问
                    queue.append((next_word, level + 1))
    
    return 0  # 如果没有找到有效的转换路径

# Example usage
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print(ladderLength(beginWord, endWord, wordList))  # Output: 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法分析

• 时间复杂度：O(N * M^2)，其中 N 是 wordList 的长度，M 是单词的长度。对每个单词，可能的变换有 M*26 种，且检查一个变换是否在 wordList 中平均需要 O(1) 时间。
• 空间复杂度：O(N)，存储 wordSet 及队列中的元素所需的空间。

算法图解与说明

考虑 beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

示意的搜索树如下：
          hit
         /
       hot
       / \
     dot lot
     /     \
   dog     log
   /
 cog

广度优先搜索首先访问 "hit" 的所有单字母变换，发现 "hot" 在列表中，然后继续探索 "hot" 的变换 "dot" 和 "lot"，依此类推，直到找到 "cog"。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种方法确保了找到的第一个解是最短的路径，因为广度优先搜索会层层递进地探索所有可能的路径，直到找到目标单词。

方法二：双向广度优先搜索（Bi-directional BFS）

双向广度优先搜索是优化单向 BFS 的一种常用策略，特别适用于在较大空间中找到两个点之间的最短路径问题。这种方法从两个方向同时进行搜索——一个从 beginWord 开始，另一个从 endWord 开始，并在中间某处相遇，从而显著减少搜索空间和时间。

解题步骤

1. 首先检查 endWord 是否在 wordList 中，如果不在，则无法转换，返回 0。
2. 使用两个集合 beginSet 和 endSet 分别存储从开始和结束词汇扩展的单词，以便从两端进行搜索。
3. 使用 visited 集合跟踪已访问的单词以避免重复处理。
4. 循环执行以下步骤，直到 beginSet 或 endSet 为空：
   • 选择较小的集合进行扩展（这样做可以减少每一步需要处理的单词数量）。
   • 为当前集合中的每个单词生成所有可能的单字母变换。
   • 如果变换后的单词在对方集合中，说明找到了连接路径，返回当前路径长度。
   • 如果变换后的单词在 wordList 中且未被访问过，将其加入临时集合并标记为已访问。
   • 更新当前扩展集合为临时集合。
5. 如果两个集合都被耗尽还没找到路径，则返回 0。

Python 示例

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    wordSet = set(wordList)
    beginSet, endSet = {beginWord}, {endWord}
    visited = set()
    step = 1
    while beginSet and endSet:
        if len(beginSet) > len(endSet):
            beginSet, endSet = endSet, beginSet
        temp = set()
        for word in beginSet:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in endSet:
                        return step + 1
                    if next_word in wordSet and next_word not in visited:
                        temp.add(next_word)
                        visited.add(next_word)
        beginSet = temp
        step += 1
    return 0

# Example usage
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print(ladderLength(beginWord, endWord, wordList))  # Output: 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

算法分析

• 时间复杂度：O(N * M^2)，N 是 wordList 的长度，M 是单词的长度。尽管仍然需要检查单词的所有单字母变换，但双向搜索通常比单向 BFS 快得多。
• 空间复杂度：O(N)，主要是 wordSet 和 visited 的存储空间。

算法图解与说明

考虑 beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

双向搜索树可能如下：
从 'hit' 开始:   hit -> hot -> dot -> dog 
                                      ↗
从 'cog' 开始:   cog -> dog

在 'dog' 处两边搜索相遇，总步数为 5。
1
2
3
4
5
6
7
8

双向 BFS 有效地缩短了搜索路径，通过在中间某点相遇来连接从开始和结束词汇扩展的路径，从而更快地找到最短路径。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/718584