Is Sentence Similarity II easy or hard?

Sentence Similarity II is considered a Medium difficulty problem. The challenge is recognizing that similarity is transitive and modeling it as connected components. Once you identify Union Find or graph traversal as the underlying technique, the implementation becomes straightforward.

Sentence Similarity II Python/Java solution

Most implementations build a Union Find structure using a hash map that maps each word to its parent. Similarity pairs are unioned first, then the sentences are compared word by word using find operations. The same logic works in Python, Java, C++, and Go with nearly identical structure.

How to solve Sentence Similarity II in O(n)?

Near O(n) performance is achieved with Union Find. First union all similarity pairs so connected words share the same root. Then iterate through both sentences once and check whether each word pair has the same root parent. Path compression keeps find operations almost constant time.

What is the best approach for Sentence Similarity II?

The Union Find (Disjoint Set) approach is the most efficient and commonly expected solution. It groups words into connected components using union operations on each similarity pair. After preprocessing, checking whether two words are similar is a simple root comparison. With path compression, the overall complexity is about O(n + p α(p)).

Is Sentence Similarity II asked at Google/Amazon/Meta?

Sentence Similarity II is a common interview-style problem related to graph connectivity and Union Find. Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests understanding of disjoint sets, transitive relationships, and efficient connectivity checks.

What data structure is used in Sentence Similarity II?

The main data structures are graphs and Union Find. A hash map stores adjacency lists for DFS/BFS traversal, while a disjoint set structure groups similar words into connected components. Hash tables are also used to map words to parents or neighbors efficiently.

What is the time complexity of Sentence Similarity II?

Using Union Find, the time complexity is O(n + p α(p)), where n is the sentence length and p is the number of similarity pairs. The α(p) term is the inverse Ackermann function, which is effectively constant in practice. A graph DFS/BFS solution runs in O(n + p) but may perform repeated traversals.

Description Hints 1 Solution Video 20:50

737. Sentence Similarity II

Medium51.2% acceptance4 companiesPremium elsewhere, free here

We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am",happy","with","leetcode"].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [x_i, y_i] indicates that the two words x_i and y_i are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

They have the same length (i.e., the same number of words)
sentence1[i] and sentence2[i] are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is transitive. For example, if the words a and b are similar, and the words b and c are similar, then a and c are similar.

Example 1:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true
Explanation: The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.

Example 2:

Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
Output: true
Explanation: "leetcode" --> "platform" --> "anime" --> "manga" --> "onepiece".
Since "leetcode is similar to "onepiece" and the first two words are the same, the two sentences are similar.

Example 3:

Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
Output: false
Explanation: "leetcode" is not similar to "onepiece".

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 <= x_i.length, y_i.length <= 20
x_i and y_i consist of English letters.

Asked at 4 companies

Rippling

Google Apple Amazon

Topics

Hints open one at a time

Hint 1

Consider the graphs where each pair in "pairs" is an edge. Two words are similar if they are the same, or are in the same connected component of this graph.

20:50

Still stuck?Read the written solution, or watch a walkthrough.

Open solution