Skip to main content
Talentd

Sentence Similarity II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringDepth-First Search6 min readAsked at: Amazon, Apple, Google +1
Practice this problem

Problem Statement

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] = [xi, yi] indicates that the two words xi and yi 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 <= xi.length, yi.length <= 20
  • xi and yi consist of English letters.

Approach Overview

Problem Overview: You are given two sentences and a list of similar word pairs. Words are considered similar if they are directly or indirectly connected through these pairs. The task is to determine whether the two sentences are similar by checking if each corresponding word belongs to the same similarity group.

Approach 1: Graph Traversal with DFS/BFS (O(n + p) time, O(p) space)

Treat each word as a node in a graph and every similar pair as an undirected edge. Build an adjacency list using a hash table where each word maps to its neighbors. For every position i in the sentences, if the words differ, run a DFS or BFS from the first word to see if the second word is reachable. The key insight is that similarity is transitive, so reachability in the graph determines equivalence. This works well when the number of similarity pairs is moderate and you want an explicit traversal of relationships.

Approach 2: Union Find / Disjoint Set (O(n + p α(p)) time, O(p) space)

Model the problem as connected components using Union Find. Each unique word belongs to a disjoint set. Iterate through the similarity pairs and perform union(a, b) so both words share the same root. After building the structure, compare the sentences word by word. If two words are identical, continue. Otherwise check whether find(word1) == find(word2). Path compression and union by rank keep operations nearly constant time. This approach avoids repeated graph traversals and scales better when the pair list is large.

Recommended for interviews: Union Find is typically the expected solution. It directly models the transitive similarity relationship and provides near O(1) connectivity checks after preprocessing. Implementing the DFS/BFS graph approach first demonstrates understanding of the problem as a connectivity search, while switching to Union Find shows stronger algorithmic design and optimization skills.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Traversal (DFS/BFS)O(n + p)O(p)When you want an explicit graph representation and occasional reachability checks
Union Find (Disjoint Set)O(n + p α(p))O(p)Best general solution for large synonym sets and repeated similarity queries

Video Solution

花花酱 LeetCode 737. Sentence Similarity II- 刷题找工作 EP118 • Hua Hua • 4,364 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sentence Similarity II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Accounts Merge

Next

Number of Provinces