我们可以将一个句子表示为一个单词数组，例如，句子
"I am happy with leetcode" 可以表示为 arr = ["I", "am", happy", "with", "leetcode"]给定两个句子
sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi and yi 是相似的。如果
sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。两个句子是相似的，如果:
- 它们具有 相同的长度 (即相同的字数)
- 对于每个位置
i，sentence1[i]和sentence2[i]要么完全相同，要么它们在similarPairs中被定义为相似。
请注意:
- 一个词总是与它自己相似
- 相似关系是不可传递的。
例如，如果单词
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)都是 不同 的
解法一：哈希集合存相似单词对 （推荐）
对比两个句子，需要对每个位置判断：如果两个词相等，直接通过；如果不相等，就检查它们是否是已知相似对。
最简单的做法是把所有相似单词对放进一个哈希集合。
由于单词对的相似关系是对称的，有两种写法：
- 只存原始
(x, y)，查询时同时查(x, y)和(y, x)；
- 预处理时把
(x, y)和(y, x)都存进去，查询时只查一次。
第一种写法更省一点空间， 哈希集合里的 key 是一个二元组
(x, y)，这样查相似关系就是平均 O(1) 。复杂度分析
设
n 是句子中的单词数，k 是 similarPairs 的数量，m 是单词平均长度。- 时间复杂度：
O((n + k) * m) - 构建哈希集合需要处理
k个相似对:O(k * m) - 逐词比较两个句子需要
n次字符串比较和哈希查询，时间复杂度是O(n * m)
- 空间复杂度：
O(k * m)
用于存储所有相似单词对。
解法二：哈希表 + 哈希集合
另一种写法是建立一个映射：
word_to_similar[word] = set(所有与 word 相似的词)比如，
similarPairs = [["great", "fine"], ["acting", "drama"]] 可以建成：这样比较
sentence1[i] 和 sentence2[i] 时，只需要判断 sentence2[i] in word_to_similar[sentence1[i]]这个写法的好处是语义更明确：每个单词直接对应一组相似词。尤其当一个词有很多相似词时，哈希集合查询仍然是平均
O(1)。复杂度分析
设：
n 是句子长度，k 是相似单词对数量，m 是单词平均长度。- 时间复杂度：
O((n + k) * m)
- 空间复杂度是：
O(k * m)
因为每个相似对会被双向存储。
总结
这题按位置比较两个句子。两个句子长度不同一定不相似；长度相同时，每个位置上的两个单词要么相等，要么必须是题目给出的相似单词对。因为相似关系是对称但不传递的，所以不需要并查集。
这两种写法本质完全一样，都是用哈希结构加速“两个词是否直接相似”的查询。
区别只是存储形式不同：
- 哈希集合：存 pair，例如 ("great", "fine")
- 哈希表 + 哈希集合： 存 adjacency list，例如 great -> {fine}
只需要判断直接相似关系，哈希集合已经足够。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-734-句子相似性
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 729] 日程安排 1
下一篇
[Leetcode 737] 句子相似性 II