题目描述
这是 LeetCode 上的 127. 单词接龙 ,难度为 困难。
Tag : 「双向 BFS」
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列:
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 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 中的所有字符串 互不相同
基本分析
根据题意,每次只能替换一个字符,且每次产生的新单词必须在 wordList
出现过。
一个朴素的实现方法是,使用 BFS 的方式求解。
从 beginWord
出发,枚举所有替换一个字符的方案,如果方案存在于 wordList
中,则加入队列中,这样队列中就存在所有替换次数为 11 的单词。然后从队列中取出元素,继续这个过程,直到遇到 endWord
或者队列为空为止。
同时为了「防止重复枚举到某个中间结果」和「记录每个中间结果是经过多少次转换而来」,我们需要建立一个「哈希表」进行记录。
哈希表的 KV 形式为 { 单词 : 由多少次转换得到 }
。
当枚举到新单词 str
时,需要先检查是否已经存在与「哈希表」中,如果不存在则更新「哈希表」并将新单词放入队列中。
这样的做法可以确保「枚举到所有由 beginWord
到 endWord
的转换路径」,并且由 beginWord
到 endWord
的「最短转换路径」必然会最先被枚举到。
双向 BFS
经过分析,BFS 确实可以做,但本题的数据范围较大:1 <= beginWord.length <= 10
朴素的 BFS 可能会带来「搜索空间爆炸」的情况。
想象一下,如果我们的 wordList
足够丰富(包含了所有单词),对于一个长度为 1010 的 beginWord
替换一次字符可以产生 10 * 2510∗25 个新单词(每个替换点可以替换另外 2525 个小写字母),第一层就会产生 250250 个单词;第二层会产生超过 6 * 10^46∗104 个新单词 ...
随着层数的加深,这个数字的增速越快,这就是「搜索空间爆炸」问题。
在朴素的 BFS 实现中,空间的瓶颈主要取决于搜索空间中的最大宽度。
那么有没有办法让我们不使用这么宽的搜索空间,同时又能保证搜索到目标结果呢?
「双向 BFS」 可以很好的解决这个问题:
同时从两个方向开始搜索,一旦搜索到相同的值,意味着找到了一条联通起点和终点的最短路径。
「双向 BFS」的基本实现思路如下:
- 创建「两个队列」分别用于两个方向的搜索;
- 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」;
- 为了尽可能让两个搜索方向“平均”,每次从队列中取值进行扩展时,先判断哪个队列容量较少;
- 如果在搜索过程中「搜索到对方搜索过的节点」,说明找到了最短路径。
「双向 BFS」基本思路对应的伪代码大致如下:
d1、d2 为两个方向的队列 m1、m2 为两个方向的哈希表,记录每个节点距离起点的 // 只有两个队列都不空,才有必要继续往下搜索 // 如果其中一个队列空了,说明从某个方向搜到底都搜不到该方向的目标节点 while(!d1.isEmpty() && !d2.isEmpty()) { if (d1.size() < d2.size()) { update(d1, m1, m2); } else { update(d2, m2, m1); } } // update 为从队列 d 中取出一个元素进行「一次完整扩展」的逻辑 void update(Deque d, Map cur, Map other) {} 复制代码
回到本题,我们看看如何使用「双向 BFS」进行求解。
估计不少同学是第一次接触「双向 BFS」,因此这次我写了大量注释。
建议大家带着对「双向 BFS」的基本理解去阅读。
代码:
class Solution { String s, e; Set<String> set = new HashSet<>(); public int ladderLength(String _s, String _e, List<String> ws) { s = _s; e = _e; // 将所有 word 存入 set,如果目标单词不在 set 中,说明无解 for (String w : ws) set.add(w); if (!set.contains(e)) return 0; int ans = bfs(); return ans == -1 ? 0 : ans + 1; } int bfs() { // d1 代表从起点 beginWord 开始搜索(正向) // d2 代表从结尾 endWord 开始搜索(反向) Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque(); /* * m1 和 m2 分别记录两个方向出现的单词是经过多少次转换而来 * e.g. * m1 = {"abc":1} 代表 abc 由 beginWord 替换 1 次字符而来 * m1 = {"xyz":3} 代表 xyz 由 endWord 替换 3 次字符而来 */ Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); d1.add(s); m1.put(s, 0); d2.add(e); m2.put(e, 0); /* * 只有两个队列都不空,才有必要继续往下搜索 * 如果其中一个队列空了,说明从某个方向搜到底都搜不到该方向的目标节点 * e.g. * 例如,如果 d1 为空了,说明从 beginWord 搜索到底都搜索不到 endWord,反向搜索也没必要进行了 */ while (!d1.isEmpty() && !d2.isEmpty()) { int t = -1; // 为了让两个方向的搜索尽可能平均,优先拓展队列内元素少的方向 if (d1.size() <= d2.size()) { t = update(d1, m1, m2); } else { t = update(d2, m2, m1); } if (t != -1) return t; } return -1; } // update 代表从 deque 中取出一个单词进行扩展, // cur 为当前方向的距离字典;other 为另外一个方向的距离字典 int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) { // 获取当前需要扩展的原字符串 String poll = deque.pollFirst(); int n = poll.length(); // 枚举替换原字符串的哪个字符 i for (int i = 0; i < n; i++) { // 枚举将 i 替换成哪个小写字母 for (int j = 0; j < 26; j++) { // 替换后的字符串 String sub = poll.substring(0, i) + String.valueOf((char)('a' + j)) + poll.substring(i + 1); if (set.contains(sub)) { // 如果该字符串在「当前方向」被记录过(拓展过),跳过即可 if (cur.containsKey(sub)) continue; // 如果该字符串在「另一方向」出现过,说明找到了联通两个方向的最短路 if (other.containsKey(sub)) { return cur.get(poll) + 1 + other.get(sub); } else { // 否则加入 deque 队列 deque.addLast(sub); cur.put(sub, cur.get(poll) + 1); } } } } return -1; } } 复制代码
- 时间复杂度:令
wordList
长度为 nn,beginWord
字符串长度为 mm。由于所有的搜索结果必须都在wordList
出现过,因此算上起点最多有 n + 1n+1 节点,最坏情况下,所有节点都联通,搜索完整张图复杂度为 O(n^2)O(n2) ;从beginWord
出发进行字符替换,替换时进行逐字符检查,复杂度为 O(m)O(m)。整体复杂度为 O(m * n^2)O(m∗n2) - 空间复杂度:同等空间大小。O(m * n^2)O(m∗n2)
总结
这本质其实是一个「所有边权均为 1
」最短路问题:将 beginWord
和所有在 wordList
出现过的字符串看做是一个点。每一次转换操作看作产生边权为 1
的边。问题求以 beginWord
为源点,以 endWord
为汇点的最短路径。
借助这个题,我向你介绍了「双向 BFS」,「双向 BFS」可以有效解决「搜索空间爆炸」问题。
对于那些搜索节点随着层数增加呈倍数或指数增长的搜索问题,可以使用「双向 BFS」进行求解。
【补充】启发式搜索 AStar
可以直接根据本题规则来设计 A* 的「启发式函数」。
比如对于两个字符串 a
b
直接使用它们不同字符的数量来充当估值距离,我觉得是合适的。
因为不同字符数量的差值可以确保不会超过真实距离(是一个理论最小替换次数)。
注意:本题数据比较弱,用 A* 过了,但通常我们需要「确保有解」,A* 的启发搜索才会发挥真正价值。而本题,除非 endWord
本身就不在 wordList
中,其余情况我们无法很好提前判断「是否有解」。这时候 A* 将不能带来「搜索空间的优化」,效果不如「双向 BFS」。
Java 代码:
class Solution { class Node { String str; int val; Node (String _str, int _val) { str = _str; val = _val; } } String s, e; int INF = 0x3f3f3f3f; Set<String> set = new HashSet<>(); public int ladderLength(String _s, String _e, List<String> ws) { s = _s; e = _e; for (String w : ws) set.add(w); if (!set.contains(e)) return 0; int ans = astar(); return ans == -1 ? 0 : ans + 1; } int astar() { PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val); Map<String, Integer> dist = new HashMap<>(); dist.put(s, 0); q.add(new Node(s, f(s))); while (!q.isEmpty()) { Node poll = q.poll(); String str = poll.str; int distance = dist.get(str); if (str.equals(e)) { break; } int n = str.length(); for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) { String sub = str.substring(0, i) + String.valueOf((char)('a' + j)) + str.substring(i + 1); if (!set.contains(sub)) continue; if (!dist.containsKey(sub) || dist.get(sub) > distance + 1) { dist.put(sub, distance + 1); q.add(new Node(sub, dist.get(sub) + f(sub))); } } } } return dist.containsKey(e) ? dist.get(e) : -1; } int f(String str) { if (str.length() != e.length()) return INF; int n = str.length(); int ans = 0; for (int i = 0; i < n; i++) { ans += str.charAt(i) == e.charAt(i) ? 0 : 1; } return ans; } } 复制代码
Python 3 代码:
class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: class PriorityQueue: def __init__(self): self.queue = [] self.explored = set() def __contains__(self, item): return item in self.explored def __add__(self, other): heapq.heappush(self.queue, other) self.explored.add(other[2]) def __len__(self): return len(self.queue) def pop(self): return heapq.heappop(self.queue) def heuristic(curr, target): return sum(1 for a, b in zip(curr, target) if a != b) wordList = set(wordList) if endWord not in wordList: return 0 front = PriorityQueue() front.__add__((1, 0, beginWord)) while front: l, _, s = front.pop() if s == endWord: return l for i in range(len(s)): for c in string.ascii_lowercase: t = s[:i] + c + s[i + 1:] if t in wordList and t not in front: front.__add__((l + 1, heuristic(t, endWord), t)) return 0 复制代码
最后
这是我们「刷穿 LeetCode」系列文章的第 No.127
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。