Problem Breakdown
We need to determine if two sentences (words1, words2) are “similar”. Two conditions must be met:
- Length Match: The number of words in both sentences must be identical. If not, they cannot be similar.
- Word Similarity: For every index , the word at that position (
words1[i],words2[i]) must either be exactly equal OR belong to a connected component defined by the similarity pairs.
The key properties of this relationship are:
- Symmetric: If A is similar to B, then B is similar to A.
- Transitive: If A ~ B and B ~ C, then A ~ C. This implies we can treat words as nodes in a graph where pairs define edges. Similarity exists if two words are in the same connected component (or identical).
Inputs: words1, words2 (lists of strings), pairs (list of word lists representing similarity relations).
Output: Boolean (True or False).
Constraints/Edge Cases:
- Length mismatch is an immediate failure.
- Words in sentences might not appear in any pair; they are only similar if identical to the counterpart.
- Duplicate pairs (handled naturally by Union-Find).
Intuition
A naive approach would be to check every word pair (words1[i], words2[i]) against all pairs. If we use BFS/DFS for each query, it becomes or worse. Since similarity is transitive and symmetric, this structure strongly suggests a Disjoint Set Union (DSU) / Union-Find data structure.
We can build the graph of similar words once using pairs. Each pair (u, v) merges the sets containing u and v. After building all connections:
- If two words are identical (
words1[i] == words2[i]), they are trivially similar. - If they differ, we check if their roots in the DSU structure are the same.
This reduces the query time to nearly constant amortized time per word pair after an initial build phase.
Approach
- Length Check: Immediately return
Falseif lengths ofwords1andwords2differ. - Initialize DSU: Create a mapping for all unique words encountered in both sentences and the pairs list to initialize their parent pointers (initially pointing to themselves). This ensures we handle unseen words gracefully as isolated components.
- Build Connectivity: Iterate through each pair
(u, v)frompairs. Perform a union operation on sets containinguandv. Use path compression for efficiency during lookups. - Validate Sentences: Iterate index from 0 to length-1:
- If
words1[i] == words2[i], continue (similar). - Otherwise, check if
find(words1[i])equalsfind(words2[i]). If not, returnFalse.
- If
- Success: Return
Trueafter the loop completes without mismatches.
Complexity Analysis
- Time Complexity: , where is total words in sentences (for length check and iteration), is number of pairs, is inverse Ackermann function (nearly constant). Building the DSU takes linear time with respect to unique vocabulary size.
- Space Complexity: , where is the number of unique words across sentences and pairs, stored in the parent map for path compression/rank optimization.
Solution
class UnionFind:
def __init__(self):
self.parent = {}
def find(self, x):
if x not in self.parent:
# If a word hasn't been seen yet (not part of any pair),
# it is its own component. Initialize on demand for lazy handling.
self.parent[x] = x
return x
root = x
while root != self.parent[root]:
root = self.parent[root]
# Path compression: point all nodes along the path directly to root
curr = x
while curr != root:
next_node = self.parent[curr]
self.parent[curr] = root
curr = next_node
return root
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return
# Simple rank/size optimization is omitted for brevity but
# path compression alone gives nearly constant time.
# We attach one tree to another arbitrarily here.
self.parent[rootX] = rootY
def areSentencesSimilarII(words1, words2, pairs):
if len(words1) != len(words2):
return False
uf = UnionFind()
# Process all similarity relations first
for u, v in pairs:
uf.union(u, v)
# Check each word position
for w1, w2 in zip(words1, words2):
if w1 == w2:
continue
rootW1 = uf.find(w1)
rootW2 = uf.find(w2)
if rootW1 != rootW2:
return False
return True
# Example usage (commented out for clean submission):
# print(areSentencesSimilarII(["great", "acting"], ["fine", "drama"], [["great","good"],["fine","good"]]))
Edge Cases Handled
- Different Sentence Lengths: Checked immediately at the start; returns
False. - Identical Words in Sentences (
w1 == w2): Skipped DSU check, treated as similar. - Words Not Present in Pairs: The lazy initialization inside
find()ensures words appearing only in sentences are initialized to themselves (isolated components). If they differ from their counterpart and aren’t connected via pairs, the roots will differ correctly returningFalse. - Empty Pairs List: Loop over pairs does nothing; similarity relies solely on exact word matches.
- Duplicate/Redundant Pairs: Union-Find handles redundant edges naturally (roots already equal).