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.

Description Hints 1 Solution Video 7:19

734. Sentence Similarity

Easy44.5% acceptance1 companyPremium 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 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 <= x_i.length, y_i.length <= 20
x_i and y_i consist of lower-case and upper-case English letters.
All the pairs (x_i,y_i) are distinct.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Two words w1 and w2 are similar if and only if w1 == w2, (w1, w2) was a pair, or (w2, w1) was a pair.

7:19

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

Open solution