Domain 1EasyCORE

Sentence Similarity

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

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:

  1. They have the same length.
  2. 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 sentence1 and sentence2 differ, they cannot be similar.
  • A word is always similar to itself.
  • The similarity relation is not transitive (i.e., if a is similar to b, and b is similar to c, it does not imply that a is similar to c).

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

  1. Check Lengths: First, check if the lengths of sentence1 and sentence2 are equal. If not, return false.
  2. 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.
  3. Iterate and Compare Words: For each pair of corresponding words in sentence1 and sentence2, check if they are identical or if one is in the similarity set of the other. If any pair does not meet these conditions, return false.
  4. 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 false if the lengths of sentence1 and sentence2 differ.
  • Self-Similarity: Each word is inherently similar to itself, so no additional handling is needed for this case.
  • No Similar Pairs: If similarPairs is empty, the function will only return true if all corresponding words in the sentences are identical.