734. Sentence Similarity
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 42.4%
Problem Breakdown
The problem requires determining if two sentences are similar based on given pairs of similar words. The inputs are:
sentence1: An array of strings representing the first sentence.sentence2: An array of strings representing the second sentence.similarPairs: A list of string pairs where each pair indicates that the two words in the pair are similar.
The output is a boolean value indicating whether the two sentences are similar. Two sentences are considered similar if:
- They have the same length.
- Each corresponding word in the sentences is either identical or part of a given similar pair.
Implicit constraints and edge cases include:
- If the lengths of
sentence1andsentence2differ, they cannot be similar. - A word is always similar to itself.
- The similarity relation is not transitive (i.e., if
ais similar tob, andbis similar toc, it does not imply thatais similar toc).
Intuition
A brute-force approach would involve checking each pair of words in the sentences against all pairs in similarPairs. This approach has a time complexity of O(n * m), where n is the length of the sentences and m is the number of similar pairs. This is inefficient for larger inputs.
The key insight to improve this is to use a hash table (dictionary) to store each word from similarPairs along with its corresponding similar words. This allows for constant-time lookups when checking if two words are similar, reducing the overall time complexity to O(n).
Approach
- Check Lengths: First, check if the lengths of
sentence1andsentence2are equal. If not, returnfalse. - Build Similarity Dictionary: Create a dictionary where each key is a word from
similarPairs, and the value is a set of words that are similar to it. - Iterate and Compare Words: For each pair of corresponding words in
sentence1andsentence2, check if they are identical or if one is in the similarity set of the other. If any pair does not meet these conditions, returnfalse. - Return True: If all pairs of words are similar, return
true.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of the sentences and m is the number of similar pairs. Building the dictionary takes O(m) time, and checking each pair of words takes O(n) time.
- Space Complexity: O(m), for storing the similarity dictionary.
Solution
def areSentencesSimilar(sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
if len(sentence1) != len(sentence2):
return False
# Build a dictionary to store similar words
similarity_dict = {}
for word1, word2 in similarPairs:
if word1 not in similarity_dict:
similarity_dict[word1] = set()
if word2 not in similarity_dict:
similarity_dict[word2] = set()
similarity_dict[word1].add(word2)
similarity_dict[word2].add(word1)
# Check each pair of words
for w1, w2 in zip(sentence1, sentence2):
if w1 != w2 and (w1 not in similarity_dict or w2 not in similarity_dict[w1]):
return False
return True
Edge Cases Handled
- Different Lengths: The function immediately returns
falseif the lengths ofsentence1andsentence2differ. - Self-Similarity: Each word is inherently similar to itself, so no additional handling is needed for this case.
- No Similar Pairs: If
similarPairsis empty, the function will only returntrueif all corresponding words in the sentences are identical.