我们可以将一个句子表示为一个单词数组，例如，句子
I am happy with leetcode"可以表示为 arr = ["I","am",happy","with","leetcode"]给定两个句子
sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi 和 yi 是相似的。如果
sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。两个句子是相似的，如果:
- 它们具有 相同的长度 (即相同的词数)
sentence1[i]和sentence2[i]是相似的
请注意，一个词总是与它自己相似，也请注意，相似关系是可传递的。例如，如果单词
a 和 b 是相似的，单词 b 和 c 也是相似的，那么 a 和 c 也是 相似 的。示例 1:
示例 2:
示例 3:
说明:
1 <= sentence1.length, sentence2.length <= 1000
1 <= sentence1[i].length, sentence2[i].length <= 20
sentence1[i]和sentence2[i]只包含大小写英文字母
0 <= similarPairs.length <= 2000
similarPairs[i].length == 2
1 <= xi.length, yi.length <= 20
xi和yi只含英文字母
和 Sentence Similarity I 不同 的是：相似关系不仅有对称性，还具有传递性。
“传递性” 表示 如果有
great ~ good 和 good ~ fine，那么可以推出 great ~ fine。所以这题不能只查
(word1, word2) 是否直接出现在 similarPairs 中。我们要判断的是：两个词在相似关系图中是否连通。这就自然导向两种解法：
- 把相似词对建成无向图，然后对每对单词做 DFS / BFS 查连通性；
- 用并查集把每个连通块合并起来，然后判断两个词是否属于同一个集合。
解法一：Graph + DFS
最直观的建模是图。每个单词是图里的一个节点。每个相似词对
[a, b] 是一条无向边。构图后，对于句子中每个位置
i：- 如果
sentence1[i] == sentence2[i]，直接通过；
- 否则，从
sentence1[i]出发做 DFS，看能不能走到sentence2[i]。
如果所有位置都能通过，两个句子相似。
DFS 正好适合回答这个问题：从一个节点出发，能否到达另一个节点？
Walk Through Example
逐位比较时，
"i" 和 "i" 相同，直接通过；
"really" 可以通过边到 "very"；
"like" 可以到 "love"；
"apples" 可以到 "oranges"。所有位置都满足，所以返回
True。如果把
"oranges" 换成 "bananas"，而图中没有从 "apples" 到 "bananas" 的路径，就返回 False。递归 DFS
迭代 DFS
递归 DFS 写起来直观，但 Python 有递归深度限制。如果相似链很长，比如超过一千层，可能触发递归栈问题，可以改成迭代 DFS。
复杂度分析
设：
n 是句子长度；V 是图中不同单词数量；E 是相似词对数量。时间复杂度:
O(n * (V + E))- 构图时间是
O(E)，
- 每次 DFS 最坏需要遍历整个图，时间是
O(V + E)。如果句子里有n对单词都需要搜索, 就是O(n * (V + E))。
空间复杂度:
O(V + E)- 图 占
O(V + E)，
- 每次 DFS 的
visited和栈最多占O(V)。
解法二：Graph + BFS
BFS 和 DFS 本质一样，都是在图中查从一个词能不能到另一个词。
DFS 用栈，BFS 用队列。对于这题来说，两者复杂度相同，区别只是遍历顺序不同。
BFS 的写法通常更适合解释“按层扩展”，也避免递归深度问题。
复杂度分析：和 DFS 一样。BFS 是 DFS 的等价替代，不是复杂度优化。
解法三：并查集 Union-Find （推荐）
DFS / BFS 是直观解法，但每次查询都在图里重新找路径。如果
n 很大，会重复做很多连通性查询。并查集 Union-Find 是把图中的连通关系压缩成集合关系。先把所有连通块预处理出来，后续查询就非常快。
如果我们反复问：
word1 和 word2 是否在同一个相似词连通块里？那这就是并查集的经典场景。
每个相似词对
[a, b] 都执行 union(a, b)，表示它们属于同一个集合。最后比较句子时，只需要判断两个词的根节点是否相同：
find(w1) == find(w2)。
如果两个词根节点相同，说明它们在同一个连通块中，也就是相似。复杂度分析
设：
n 是句子长度；E 是相似词对数量；V 是不同单词数量。时间复杂度：
O((E + n))- 构建并查集需要对每个相似词对做一次
union，时间接近：O(E * α(V))
- 逐位比较句子需要最多
n次find，时间接近：O(n * α(V))
其中
α(V) 是反阿克曼函数，增长极慢，在实际中可以近似看成常数。所以总时间复杂度：
O((E + n) * α(V))- 空间复杂度：
O(V)
用于保存每个单词的父节点。
总结
这题的关键是相似关系具有传递性，所以不能只判断两个词是否直接出现在
similarPairs 中。应该把 similarPairs 看成一张无向图，两个词相似等价于它们在同一个连通分量里。- DFS / BFS 图搜索 是在线查询连通性：每比较一对单词，就跑一次图搜索找路径。
时间复杂度是
O(n * (V + E))，空间复杂度是O(V + E)
- Union-Find 是离线预处理连通分量：先把所有能连通的词归到同一组，每比较一对单词只需查询它们是不是同一组。
时间复杂度接近
O(E + n)，空间复杂度O(V)。
这题有很多次对应单词比较，所以并查集更适合。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-737-句子相似性-ii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 734] 句子相似性
下一篇
[Leetcode 772] 基础计算器 III