花花酱 LeetCode 734. Sentence Similarity - 刷题找工作 EP117
Sentence Similarity - Video Solution
Watch 8 video solutions for Sentence Similarity, a easy level problem involving Array, Hash Table, String. This walkthrough by Hua Hua has 2,817 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]andsentence2[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]andsentence2[i]consist of English letters.0 <= similarPairs.length <= 1000similarPairs[i].length == 21 <= xi.length, yi.length <= 20xiandyiconsist 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.
Complexity Analysis
| 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 |