We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sentence Similarity III

Number: 1923

Difficulty: Medium

Paid? No

Companies: TikTok, Google

Problem Description

Given two sentences (strings) composed of words separated by a single space, determine if they are similar. Two sentences are similar if it is possible to insert an arbitrary (possibly empty) sentence into one of them (with proper spacing) such that they become equal.

Key Insights

  • Split each sentence into an array of words.
  • Use two pointers: one from the beginning (to identify a common prefix) and one from the end (to identify a common suffix).
  • The insertion (if needed) must occur in the middle, so after matching prefix and suffix, one sentence may have extra words in the middle.
  • If the sum of the matching prefix and suffix lengths is at least the length of the shorter sentence, the sentences are similar.

Space and Time Complexity

Time Complexity: O(n) where n is the number of words in the sentences. Space Complexity: O(n) for storing the split words.

Solution

The solution uses a two-pointer approach:

  1. Split both sentences by spaces.
  2. Initialize a pointer from the start and count how many words match in order.
  3. Initialize another pointer from the end and count how many words match in reverse order (while ensuring no overlap with the prefix).
  4. If the total number of matching words (from the beginning and the end) is greater than or equal to the number of words in the shorter sentence, then the sentences are similar.
  5. Otherwise, they are not similar.

This approach effectively verifies if one sentence can be transformed into the other by inserting extra words in between the matched parts.

Code Solutions

# Python solution for Sentence Similarity III

def areSentencesSimilar(sentence1, sentence2):
    # Split both sentences into list of words
    words1 = sentence1.split(" ")
    words2 = sentence2.split(" ")
    
    # Initialize pointer for prefix matching
    left = 0
    # Match words from the beginning until a mismatch occurs
    while left < len(words1) and left < len(words2) and words1[left] == words2[left]:
        left += 1
    
    # Initialize pointer for suffix matching
    right = 0
    # Match words from the end until a mismatch occurs
    while (right < (len(words1) - left)) and (right < (len(words2) - left)) \
          and words1[len(words1) - 1 - right] == words2[len(words2) - 1 - right]:
        right += 1
    
    # If the sum of matching words (from left and right) is at least the length of the shorter sentence,
    # then the sentences are similar.
    return left + right >= min(len(words1), len(words2))

# Example usage:
print(areSentencesSimilar("My name is Haley", "My Haley"))  # Expected output: True
← Back to All Questions