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:
sentence1[i] and sentence2[i] are similar.Notice that a word is always similar to itself, also notice that the similarity relation is not transitive. For example, if the words a and b are similar, and the words b and c are similar, a and c are not necessarily similar.
Example 1:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["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 = ["great"], sentence2 = ["great"], similarPairs = [] Output: true Explanation: A word is similar to itself.
Example 3:
Input: sentence1 = ["great"], sentence2 = ["doubleplus","good"], similarPairs = [["great","doubleplus"]] Output: false Explanation: As they don't have the same length, we return false.
Constraints:
1 <= sentence1.length, sentence2.length <= 10001 <= sentence1[i].length, sentence2[i].length <= 20sentence1[i] and sentence2[i] consist of English letters.0 <= similarPairs.length <= 1000similarPairs[i].length == 21 <= xi.length, yi.length <= 20xi and yi consist of lower-case and upper-case English letters.(xi, yi) are distinct.Problem Overview: You receive two sentences represented as arrays of words and a list of similar word pairs. Two sentences are considered similar if they have the same length and each corresponding pair of words is either identical or appears in the similarity list. Similarity is not transitive, so only the direct pairs matter.
Approach 1: Brute Force Pair Lookup (O(n * p) time, O(1) space)
Iterate through both sentences word by word. For each position i, check if sentence1[i] equals sentence2[i]. If not, scan the entire list of similar pairs to see whether the two words appear as a pair in either order. This approach uses simple iteration and string comparison without extra data structures. The downside is the repeated linear search over the pairs list, which makes the algorithm slow when the number of similarity pairs grows.
Approach 2: Hash Table for Constant-Time Lookup (O(n + p) time, O(p) space)
Store all similarity pairs in a hash-based structure such as a set or adjacency map. Insert both directions of each pair, e.g., (great, good) and (good, great). Then iterate through the sentences once. For each index, check whether the words match directly or whether the pair exists in the hash table. Hash lookups run in average O(1) time, so the comparison step stays fast regardless of the number of pairs. This approach leverages a hash table to eliminate repeated scanning.
The algorithm also starts with a quick length check. If the sentences differ in length, they cannot be similar. After that, a single pass over the arrays validates every word pair. The solution combines simple iteration over an array with constant-time membership checks, which keeps the implementation clean and efficient.
Recommended for interviews: The hash table approach is what interviewers typically expect. Brute force shows that you understand the definition of similarity, but the optimized version demonstrates your ability to replace repeated searches with O(1) lookups using a string-based key structure. The result is linear time with minimal additional memory.
First, we check if the lengths of sentence1 and sentence2 are equal. If they are not equal, return false.
Then we use a hash table s to store all similar word pairs. For each word pair [x, y] in similarPairs, we add x and y to the hash table s.
Next, we traverse sentence1 and sentence2. For each position i, if sentence1[i] is not equal to sentence2[i], and (sentence1[i], sentence2[i]) and (sentence2[i], sentence1[i]) are not in the hash table s, then return false.
If the traversal ends without returning false, it means sentence1 and sentence2 are similar, so return true.
The time complexity is O(L), and the space complexity is O(L), where L is the sum of the lengths of all strings in the problem.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Scan | O(n * p) | O(1) | When similarity pair list is extremely small and simplicity is preferred |
| Hash Table Lookup | O(n + p) | O(p) | General case; optimal solution for interview and production use |
花花酱 LeetCode 734. Sentence Similarity - 刷题找工作 EP117 • Hua Hua • 2,815 views views
Watch 6 more video solutions →Practice Sentence Similarity with our built-in code editor and test cases.
Practice on FleetCode