737. Sentence Similarity II
Asked at Rippling
Difficulty
Medium
Time
O((P + L) * α(W))
Space
O(W)
Pattern
Array
Companies
1
Problem
You are given two sentences, each written as an array of words. You are also given a list of word pairs similarPairs, where each pair [x, y] means the words x and y are similar.
Two sentences are similar when two things hold: they have the same number of words, and for every position i, the word sentence1[i] is similar to sentence2[i]. Return true if the sentences are similar, otherwise return false.
Similarity is transitive. A word is always similar to itself. If a is similar to b, and b is similar to c, then a is similar to c — even if the pair [a, c] never appears in the list. So the pairs form groups of words that are all similar to each other.
Match words position by position
Constraints
- ●
1 <= sentence1.length, sentence2.length <= 1000 - ●
1 <= sentence1[i].length, sentence2[i].length <= 20 - ●
sentence1[i] and sentence2[i] consist of lower-case and upper-case English letters - ●
0 <= similarPairs.length <= 2000 - ●
similarPairs[i].length == 2 - ●
1 <= xi.length, yi.length <= 20 - ●
xi and yi consist of English letters
Examples
sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]truesentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]truesentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]falseAsked At
1 companies| 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.
Union-Find groups the words
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
O((P + L) * α(W)) timeclass 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 TrueFrequently 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 runs in O((P + L) * α(W)) time and O(W) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.