Ricky.L的随笔
0%

LeetCode.126.单词接龙 II（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.126.单词接龙 II（困难）

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

  • 每对相邻的单词之间仅有单个字母不同。
  • 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
  • sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

题解

思路

  • 通过广度优先搜索建立图的邻接表。
    • 在发现最短转换路径时停止构建图。
    • 有可能有多条最短路径，所以发现了一条最短路径时不要立刻终止，等这一层都遍历完。
  • 通过深度优先搜索，求得最短路径。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
    fun findLadders(beginWord: String, endWord: String, wordList: List<String>): List<List<String>> {
        // 单词列表转为哈希集合，便于快速查找
        val wordSet = wordList.toSet()
        // 单词列表中没有endWord直接返回，不用搜索了
        if (!wordSet.contains(endWord)) return emptyList()

        // bfs建立图的邻接表
        val graph = mutableMapOf<String, MutableSet<String>>()
        val found = bfs(beginWord, endWord, wordSet, graph)
        if (!found) return emptyList()

        // dfs搜索
        val result = mutableListOf<List<String>>()
        val path = mutableListOf(beginWord)
        dfs(beginWord, endWord, graph, path, result)

        return result
    }

    private fun bfs(beginWord: String, endWord: String, wordSet: Set<String>, graph: MutableMap<String, MutableSet<String>>): Boolean {
        val queue = java.util.ArrayDeque<String>()
        val visited = mutableSetOf<String>()

        queue.add(beginWord)
        visited.add(beginWord)

        var found = false
        val levelVisited = mutableSetOf<String>()

        while (queue.isNotEmpty()) {
            val levelCount = queue.size
            repeat(levelCount) {
                val currentWord = queue.poll()
                val nextNodes = getNextLevelNodes(currentWord, wordSet)
                for (nextWord in nextNodes) {
                    if (visited.contains(nextWord)) continue
                    if (nextWord == endWord) {
                        found = true
                    }
                    queue.add(nextWord)
                    levelVisited.add(nextWord)

                    graph.getOrPut(currentWord, { mutableSetOf() })
                            .add(nextWord)
                }
            }

            // 在某一层发现了路径终点，就直接不继续了，这样保证路径是最短的
            if (found) break

            visited.addAll(levelVisited)
            levelVisited.clear()
        }

        return found
    }

    private fun dfs(beginWord: String, endWord: String, graph: Map<String, Set<String>>, path: MutableList<String>, result: MutableList<List<String>>) {
        if (beginWord == endWord) {
            result.add(path.toList())
            return
        }
        if (!graph.containsKey(beginWord)) return

        graph[beginWord]?.forEach { nextWord ->
            path.add(nextWord)
            dfs(nextWord, endWord, graph, path, result)
            path.removeAt(path.lastIndex)
        }
    }

    /**
     * 变化[word]每一个位置的字符，看是否存在于单词列表中，存在的话，记录为下一层的顶点
     */
    private fun getNextLevelNodes(word: String, wordSet: Set<String>): Set<String> {
        val nodes = mutableSetOf<String>()
        val chars = word.toCharArray()
        for (i in chars.indices) {
            val oldChar = chars[i]
            for (j in 0 until 26) {
                val c = 'a' + j
                if (c == oldChar) continue
                chars[i] = c
                val next = String(chars)
                if (wordSet.contains(next)) {
                    nodes.add(next)
                }
            }
            chars[i] = oldChar
        }
        return nodes
    }
}