标签: 深度优先搜索 广度优先搜索 并查集 数组 哈希表 字符串
难度: Medium
Submission
运行时间: 62 ms
内存: 19.2 MB
class Solution:
def areSentencesSimilarTwo(
self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]
) -> bool:
if (n := len(sentence1)) != len(sentence2):
return False
def dfs(x):
if x in g:
return
g[x] = k
for y in d[x]:
dfs(y)
d = defaultdict(list)
for a, b in similarPairs:
d[a].append(b)
d[b].append(a)
k, g = 0, {}
for i in range(n):
a, b = sentence1[i], sentence2[i]
if a not in g:
dfs(a)
k += 1
if g[a] != g.get(b, 0):
return False
return True
Explain
该题解使用了并查集的思想。首先，将相似单词对构建成一个无向图，然后对两个句子中的每个单词进行遍历，对于每个单词，如果它没有出现在并查集中，就对它进行深度优先搜索，将所有与它相连的单词都归属到同一个集合中，并给该集合分配一个编号。最后，对于两个句子中的每个单词，检查它们是否属于同一个集合，如果有任意一对单词不属于同一个集合，就返回 False，否则返回 True。
时间复杂度: O(m + n)
空间复杂度: O(m + n)
class Solution:
def areSentencesSimilarTwo(
self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]
) -> bool:
if (n := len(sentence1)) != len(sentence2):
return False
def dfs(x):
if x in g:
return
g[x] = k # 将单词 x 归属到当前集合 k 中
for y in d[x]: # 遍历所有与 x 相似的单词
dfs(y) # 递归处理与 x 相似的单词
d = defaultdict(list) # 存储相似单词对构成的无向图
for a, b in similarPairs:
d[a].append(b)
d[b].append(a)
k, g = 0, {} # k 为当前集合的编号，g 为单词到集合编号的映射
for i in range(n):
a, b = sentence1[i], sentence2[i]
if a not in g: # 如果单词 a 没有出现在并查集中
dfs(a) # 对单词 a 进行深度优先搜索
k += 1 # 集合编号加 1
if g[a] != g.get(b, 0): # 如果单词 a 和 b 不属于同一个集合
return False
return True
Explore
并查集是一种高效处理数据分组问题的数据结构，特别适合处理动态连通性问题，即快速判断和合并集合。在句子相似性问题中，我们需要频繁判断两个单词是否通过一系列中间单词相互连接，这种'动态连通性'是并查集的强项。使用哈希表或树虽然可以实现相似功能，但在动态查询和合并操作上，并查集提供了更优的时间复杂度，尤其是在路径压缩和按秩合并优化后。
无向图的特性要求每条边双向连接，这意味着从任一节点都可以到达与之连接的任何节点。在句子相似性问题中，如果单词a与单词b相似，则单词b也必然与单词a相似。因此，为了正确反映这一逻辑关系并使得图的遍历（如深度优先搜索）可以从任一节点双向进行，我们需要将每对相似单词双向连接。这样做也简化了图的构造和遍历过程。
在DFS过程中，如果一个单词已经被访问过，意味着它已被分配到一个特定的集合中，并且所有与它相连的单词也都已经被处理过。跳过已访问的单词可以避免重复工作和无限循环，大大提高算法的效率。优势包括减少不必要的计算和提高执行速度。风险是如果图的构建或DFS的实现错误，可能导致某些连接不被正确识别，但这主要是实现错误而非方法本身的问题。
在DFS中处理单词时，我们采用递归方式将所有相连的单词归属到同一个集合中。只有当我们从一个新的未被访问的单词启动DFS时，才意味着我们开始探索一个新的集合，因此在这时增加集合编号k是合适的。这样做确保了每次遇到未访问的单词，我们都正确地标记新的集合开始，而不是在一系列相连单词处理完后再增加，这有助于更清晰地管理不同集合的界限和识别。