Ricky.L的随笔
0%

LeetCode.127.单词接龙（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.127.单词接龙（困难）

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

  • 序列中第一个单词是 beginWord 。
  • 序列中最后一个单词是 endWord 。
  • 每次转换只能改变一个字母。
  • 转换过程中的中间单词必须是字典 wordList 中的单词。

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

提示：

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

题解

思路

  • 有一个起点、一个终点，加上一系列路径的选择，就是搜索问题。
  • 可以用深度优先搜索或广度优先搜索，每个单词就是图中一个结点。

用DFS还是BFS？为什么？

  • 题目要求最短转换序列，也就是求最短路径，用广度优先搜索用时最短，发现到达终点就直接返回。
  • 如果用深度有限搜索，遍历完所有路径还得回溯，会比较耗时。

但是搜索需要有路径选择，这就引出了下一个问题。

对于每一个单词，它的邻接单词有哪些？

  • 每次转换单词只能改变一个字母，但是单词有n个字母，不知道转换哪个，那就所有的都尝试转换一遍，看能得到哪些单词。
  • 可以提前存储好每个单词能转换到的单词，直接O(1)时间查询，可以用哈希表存储。
  • 对于转换到的单词而言，他跟转换前的单词的区别也就是那一个字符不同，其他字符都相同，并且可能有多个能转换到的单词。
    • 我们可以用对要变化的位置上加上*再加上剩余字母作为哈希表的键，单词列表作为哈希表的值。
    • 提前读取所有单词，做预处理。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        // 所有单词长度一致
        val wordLength = beginWord.length

        // key是通配词，value是这个通配词对应的所有词
        val map = mutableMapOf<String, MutableList<String>>()
        wordList.forEach { word ->
            for (i in 0 until wordLength) {
                val key = word.substring(0, i) + '*' + word.substring(i + 1, wordLength)
                val list = map.getOrDefault(key, mutableListOf())
                list.add(word)
                map[key] = list
            }
        }

        // 访问数组，防止绕环
        val visited = mutableSetOf(beginWord)

        // 广度优先搜索
        val queue = ArrayDeque<String>()
        queue.add(beginWord)
        var level = 1
        val emptyList = mutableListOf<String>()
        while (queue.isNotEmpty()) {
            val count = queue.size
            repeat(count) {
                val word = queue.poll()
                for (i in 0 until wordLength) {
                    val key = word.substring(0, i) + '*' + word.substring(i + 1, wordLength)
                    val adjacentWords = map.getOrDefault(key, emptyList)
                    adjacentWords.forEach { adjacentWord ->
                        // 加1是因为endWord也算一个步骤，要加上
                        if (adjacentWord == endWord) return level + 1
                        if (!visited.contains(adjacentWord)) {
                            visited.add(adjacentWord)
                            queue.add(adjacentWord)
                        }
                    }
                }
            }
            level++
        }
        return 0
    }
}