LeetCode Solutions Blog

Sentence Similarity

Number: 734

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Given two sentences represented as arrays of words and a list of similar word pairs, determine if the sentences are similar. Two sentences are similar if they have the same length and each corresponding pair of words is similar. Note that every word is similar to itself, and the similarity relation is not transitive.

Key Insights

First, check if both sentences have the same length.
A word is always similar to itself.
Similarity is defined only by the given pairs; it is not transitive.
Use a hash table (dictionary) to store bi-directional similar pairs for quick look-ups.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of words in the sentences and m is the number of similar pairs.
Space Complexity: O(m), for storing the similar pairs in a hash table.

Solution

Check if the two sentences have the same length; if not, return false.
Build a hash table where each word maps to a set of words it is similar to. For each pair [x, y] in similarPairs, add y to the set for x and x to the set for y.
Iterate over the words of both sentences simultaneously. For each corresponding pair, if the words are identical, continue; otherwise, check if one word appears in the similar set of the other.
If all pairs meet the similarity condition, return true; otherwise, return false.

Code Solutions

# Function to determine if two sentences are similar
def are_sentences_similar(sentence1, sentence2, similarPairs):
    # Check if sentences are of the same length
    if len(sentence1) != len(sentence2):
        return False

    # Build dictionary to store similar word pairs in both directions
    similar_dict = {}
    for word1, word2 in similarPairs:
        if word1 not in similar_dict:
            similar_dict[word1] = set()
        similar_dict[word1].add(word2)
        if word2 not in similar_dict:
            similar_dict[word2] = set()
        similar_dict[word2].add(word1)

    # Check each pair of words in the sentences
    for w1, w2 in zip(sentence1, sentence2):
        # If words are the same, continue
        if w1 == w2:
            continue
        # Check if w1 is similar to w2 explicitly
        if (w1 not in similar_dict or w2 not in similar_dict[w1]) and (w2 not in similar_dict or w1 not in similar_dict[w2]):
            return False

    return True

# Example usage:
# sentence1 = ["great", "acting", "skills"]
# sentence2 = ["fine", "drama", "talent"]
# similarPairs = [["great", "fine"], ["drama", "acting"], ["skills", "talent"]]
# print(are_sentences_similar(sentence1, sentence2, similarPairs))  # Output: True