Sentence Similarity II
Asked at Rippling
Problem
Given two sentences represented as arrays of words and a list of similar word pairs, determine if the two sentences are similar. Similarity is transitive: if word A is similar to word B, and word B is similar to word C, then A is similar to C.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | MEDIUM | View all Rippling questions → |
How to Think About It
Model the problem as a graph where each word is a node and each similar pair is an edge.
Build an adjacency list from the similarityPairs list.
For each word position, perform BFS or DFS to check if the corresponding words in both sentences are connected.
Use Union-Find to group similar words into connected components for O(1) lookups after preprocessing.
Union-Find is optimal here because it avoids repeated traversals once the components are built.
Optimal Approach
Build a Union-Find data structure over all words that appear in the similarity pairs. For each pair of corresponding words in the two sentences, check if they belong to the same connected component using the Union-Find find operation. If all pairs are in the same component, the sentences are similar. The Union-Find approach gives nearly O(1) amortized per query after an O(N) preprocessing step where N is the total number of similarity pairs.
What Trips People Up in Real Interviews
Confirm that similarity is transitive and that direction does not matter (undirected).
Clarify whether words that appear only in one sentence need to be handled specially.
Check if the two sentences must have the same length; if not, return false immediately.
Union-Find is the cleanest approach for interviews: easy to implement, easy to explain.
Edge case: a word with no similar pairs is only similar to itself.
Solution Code
class UnionFind:
def __init__(self):
self.parent = {}
self.rank = {}
def find(self, x):
if x not in self.parent:
self.parent[x] = x
self.rank[x] = 0
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
class Solution:
def areSentencesSimilarTwo(self, sentence1, sentence2, similarPairs):
if len(sentence1) != len(sentence2):
return False
uf = UnionFind()
for w1, w2 in similarPairs:
uf.union(w1, w2)
for w1, w2 in zip(sentence1, sentence2):
if w1 == w2:
continue
if uf.find(w1) != uf.find(w2):
return False
return True
Frequently Asked Questions
What is the Sentence Similarity II problem?
Given two sentences represented as arrays of words and a list of similar word pairs, determine if the two sentences are similar. Similarity is transitive: if word A is similar to word B, and word B is similar to word C, then A is similar to C.
How do you solve Sentence Similarity II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sentence Similarity II?
Sentence Similarity II is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Sentence Similarity II?
- Confirm that similarity is transitive and that direction does not matter (undirected).
- Clarify whether words that appear only in one sentence need to be handled specially.
- Check if the two sentences must have the same length; if not, return false immediately.
- Union-Find is the cleanest approach for interviews: easy to implement, easy to explain.
- Edge case: a word with no similar pairs is only similar to itself.