Taro Logo

Sentence Similarity

Easy
Asked by:
Profile picture
33 views
Topics:
ArraysStringsTwo Pointers

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 a list of similar word pairs pairs, determine if two sentences are similar.

You need to consider the following:

  • Two sentences are considered similar if they have the same number of words (i.e., the same length of their corresponding string arrays).
  • Two words are considered similar if they are identical, or exist in the pairs list.
  • Similarity is transitive. For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are considered similar.

Similarity is also symmetric. For example, "great" is similar to "fine" implies that "fine" is similar to "great".

Return true if sentence1 and sentence2 are similar, otherwise return false.

Example 1:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], pairs = [["great","fine"],["acting","drama"],["skills","talent"]]
Output: true
Explanation: The two sentences have equal lengths and each word i of sentence1 is also similar to the corresponding word in sentence2.

Example 2:

Input: sentence1 = ["great"], sentence2 = ["great"], pairs = []
Output: true
Explanation: The two sentences are identical.

Example 3:

Input: sentence1 = ["great"], sentence2 = ["fine"], pairs = []
Output: false
Explanation: The two sentences have different words and are not similar.

Example 4:

Input: sentence1 = ["great"], sentence2 = ["fine"], pairs = [["great","fine"]]
Output: true
Explanation: The two sentences have different words but are similar.

Example 5:

Input: sentence1 = ["eating","pizza"], sentence2 = ["eat","pizza"], pairs = [["eating","eat"],["lasagna","pasta"]]
Output: false

Constraints:

  • 1 <= sentence1.length, sentence2.length <= 1000
  • 1 <= sentence1[i].length, sentence2[x].length <= 20
  • sentence1[i] and sentence2[x] consist of lower-case English letters.
  • 0 <= pairs.length <= 2000
  • 0 <= pairs[i].length == 2
  • 1 <= pairs[i][0].length, pairs[i][1].length <= 20
  • pairs[i][0] and pairs[i][1] consist of lower-case English letters.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Are the sentences given as arrays of strings, and if so, what are the constraints on the length and content of the individual words (strings)?
  2. How do you define similarity? Is it based on exact word matches only, or should I consider stemming, lemmatization, or synonyms?
  3. If the sentences have different lengths, what should be the expected behavior? Is there a minimum matching percentage required to consider them similar?
  4. Are the sentences case-sensitive? Should I normalize the case before comparing words?
  5. If the order of words is different between the sentences, should they still be considered similar? If so, how should I handle different word orders?

Brute Force Solution

Approach

To determine if two sentences are similar using a brute-force approach, we directly compare words between sentences. This involves examining every possible pair of words or phrases to check for a match based on some criteria of similarity.

Here's how the algorithm would work step-by-step:

  1. Take the first sentence and the second sentence.
  2. For each word in the first sentence, compare it with every word in the second sentence.
  3. If the two words are exactly the same, count it as a match.
  4. Also, check if the pair of words exist as a similar pair based on a provided list of similar word pairs.
  5. Repeat this process for all possible pairs of words between the two sentences.
  6. Calculate the percentage of matching words between the two sentences.
  7. If the calculated percentage is greater than a predefined threshold, then we can say that the two sentences are similar.

Code Implementation

def are_sentences_similar_brute_force(sentence1, sentence2, similar_pairs, threshold):
    words_in_sentence1 = sentence1.lower().split()
    words_in_sentence2 = sentence2.lower().split()
    number_of_words_in_sentence1 = len(words_in_sentence1)
    number_of_words_in_sentence2 = len(words_in_sentence2)
    
    if number_of_words_in_sentence1 == 0 or number_of_words_in_sentence2 == 0:
        return False

    matching_word_count = 0
    
    # Iterate through all possible word pairs between sentences
    for word_from_sentence1 in words_in_sentence1:
        for word_from_sentence2 in words_in_sentence2:
            # Check for exact word match
            if word_from_sentence1 == word_from_sentence2:
                matching_word_count += 1

                continue
            
            # Check if the words are in the list of similar pairs
            if (word_from_sentence1, word_from_sentence2) in similar_pairs or \
               (word_from_sentence2, word_from_sentence1) in similar_pairs:
                matching_word_count += 1

    # Calculate the percentage of matching words.
    similarity_percentage = (matching_word_count / max(number_of_words_in_sentence1, number_of_words_in_sentence2)) * 100

    # Return True if similarity is above the threshold
    return similarity_percentage > threshold

Big(O) Analysis

Time Complexity
O(n*m*k) – The outer loop iterates through each of the n words in the first sentence. The inner loop iterates through each of the m words in the second sentence. Inside the inner loop, we perform a constant-time comparison to check if the words are identical. Additionally, we check if the pair of words exist in a list of similar word pairs which takes up to k iterations where k represents the number of similar word pairs. Therefore, the total number of operations approximates n * m * k, which simplifies to O(n*m*k).
Space Complexity
O(K) – The primary space complexity comes from storing the list of similar word pairs. Let K be the number of similar word pairs provided as input. We need to store these K pairs, contributing O(K) space. Other variables used in the comparison, such as index counters, occupy constant space. Therefore, the auxiliary space required is primarily determined by the size of the similar word pairs list, resulting in O(K) space complexity.

Optimal Solution

Approach

To efficiently determine sentence similarity, we leverage a set data structure for quick lookups. We pre-process the word pairs into sets to enable constant-time checks for similarity, allowing for fast comparison of sentences.

Here's how the algorithm would work step-by-step:

  1. First, convert each pair of similar words into a set. This allows us to quickly check if two words are considered similar.
  2. Next, break each sentence into individual words.
  3. For each word in the first sentence, compare it to the corresponding word in the second sentence. They are considered similar if they are the exact same word, or if they exist as a pair of similar words in one of our sets.
  4. If we find any words that are not considered similar, the sentences are not similar. Otherwise, if all words match or are considered similar, the sentences are similar.

Code Implementation

def are_sentences_similar(sentence1, sentence2, similar_pairs):
    # Create a set of similar word pairs for fast lookup
    similar_word_pair_sets = set()
    for pair in similar_pairs:
        similar_word_pair_sets.add(tuple(pair))

    words1 = sentence1.split()
    words2 = sentence2.split()

    if len(words1) != len(words2):
        return False

    # Iterate through the words and compare them
    for i in range(len(words1)):
        word1 = words1[i]
        word2 = words2[i]

        # Check if the words are identical or in similar pairs
        if word1 == word2:
            continue

        # Check if the reverse of the pair also exists
        if (word1, word2) in similar_word_pair_sets or (word2, word1) in similar_word_pair_sets:
            continue

        # If none of the conditions are met, words are not similar
        return False

    # If all words are similar, return True
    return True

Big(O) Analysis

Time Complexity
O(n + p) – The algorithm iterates through the sentences, which takes O(n) time where n is the number of words in the longer sentence. Creating sets from the pairs takes O(p) time, where p is the number of word pairs. The set lookups during the sentence comparison are considered O(1) because sets provide constant time average-case complexity for lookups. Therefore, the dominant factors are the sentence iteration and the initial set construction, resulting in a time complexity of O(n + p).
Space Complexity
O(P) – The primary space usage comes from converting the word pairs into sets, where P is the number of word pairs. We create a set for each pair of similar words to facilitate quick lookups. The space required to store these sets is proportional to the number of pairs, P, provided as input.

Edge Cases

One or both input sentence arrays are null or empty
How to Handle:
Return True if both are empty, False if only one is, based on problem definition.
Input sentences have significantly different lengths
How to Handle:
If sentence lengths differ, return False immediately as they cannot be similar if not of equal length.
The word pairs array is null or empty
How to Handle:
If the word pairs array is empty, sentence similarity depends on exact string equality, so check that.
The word pairs array contains null or empty strings
How to Handle:
Handle null or empty strings by skipping the pair and continuing, or consider it as non-similar if appropriate for the problem.
The word pairs array contains duplicate word pairs
How to Handle:
The union find or graph approach handles this naturally as the root will still be the same for the connected components.
Sentences contain words with different casing ('The' vs 'the')
How to Handle:
Convert all words to lowercase before comparison to ensure case-insensitive matching.
Sentences contain punctuation or special characters
How to Handle:
Remove punctuation and special characters from words before comparison, or handle them explicitly as part of the comparison.
Maximum length sentences exceeding memory constraints for large input sizes
How to Handle:
Consider using a more memory-efficient data structure or algorithm, or reject overly long inputs gracefully.