Skip to main content
Talentd

Sentence Similarity - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash TableString10 min readAsked at: Google
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 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 <= 1000
  • 1 <= sentence1[i].length, sentence2[i].length <= 20
  • sentence1[i] and sentence2[i] consist of English letters.
  • 0 <= similarPairs.length <= 1000
  • similarPairs[i].length == 2
  • 1 <= xi.length, yi.length <= 20
  • xi and yi consist of lower-case and upper-case English letters.
  • All the pairs (xi, yi) are distinct.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ScanO(n * p)O(1)When similarity pair list is extremely small and simplicity is preferred
Hash Table LookupO(n + p)O(p)General case; optimal solution for interview and production use

Video Solution

花花酱 LeetCode 734. Sentence Similarity - 刷题找工作 EP117 • Hua Hua • 2,817 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Sentence Similarity easy or hard?
Sentence Similarity is classified as an Easy problem. The core logic involves iterating through two arrays and checking membership in a hash table. The challenge mainly lies in recognizing that similarity is not transitive and ensuring both sentences have the same length.
Sentence Similarity Python/Java solution
Most implementations create a set of word pairs such as (word1, word2) and (word2, word1). Then the algorithm iterates through both sentence arrays and verifies equality or membership in the set. This pattern works the same in Python, Java, C++, Go, TypeScript, and other languages.
How to solve Sentence Similarity in O(n)?
Store every similarity pair in a hash set or adjacency map for constant-time lookup. Then iterate through both sentences once. For each index, check if the words are equal or if the pair exists in the set. This avoids repeatedly scanning the pairs list and keeps the algorithm close to linear time.
What is the best approach for Sentence Similarity?
The most efficient solution uses a hash table (set or map) to store all similarity pairs. Each pair is inserted in both directions, allowing constant-time lookup during comparison. After building the structure in O(p) time, you scan both sentences once in O(n), making the overall complexity O(n + p).
Is Sentence Similarity asked at Google/Amazon/Meta?
Sentence comparison and word relationship problems appear in interviews at companies like Amazon, Google, and Meta, especially in early rounds. The problem tests basic hash table usage, string comparison, and careful handling of edge cases such as mismatched sentence lengths.
What data structure is used in Sentence Similarity?
A hash table is the primary data structure. It stores pairs of similar words so the algorithm can check similarity using O(1) average-time lookups. Arrays store the sentence words, while the hash table tracks relationships between strings.
What is the time complexity of Sentence Similarity?
The optimal solution runs in O(n + p) time, where n is the number of words in the sentences and p is the number of similarity pairs. Building the hash table requires O(p), and comparing each word position requires O(n). Space complexity is O(p) for storing the pairs.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Accounts Merge

Next

Number of Provinces