{x}
blog image

Sentence Similarity III

You are given two strings sentence1 and sentence2, each representing a sentence composed of words. A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.

Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. Note that the inserted sentence must be separated from existing words by spaces.

For example,

  • s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.
  • s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

 

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"

Output: true

Explanation:

sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"

Output: false

Explanation:

No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"

Output: true

Explanation:

sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

 

Constraints:

  • 1 <= sentence1.length, sentence2.length <= 100
  • sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
  • The words in sentence1 and sentence2 are separated by a single space.

Solution Explanation: Sentence Similarity III

This problem asks whether two sentences are similar, meaning one can be transformed into the other by inserting a sentence in the middle. The solution leverages a two-pointer approach for efficient comparison.

Algorithm:

  1. Split Sentences: The input sentences (sentence1, sentence2) are first split into arrays of words (words1, words2).

  2. Handle Length Difference: The algorithm handles the case where one sentence is shorter than the other. It ensures that words1 always refers to the longer sentence. This simplifies the subsequent comparison logic.

  3. Two-Pointer Comparison: Two pointers, i and j, are initialized to 0.

    • Pointer i iterates from the beginning of both sentences, comparing words from the start. It increments as long as the words at the current index are identical in both sentences.
    • Pointer j iterates from the end of both sentences, comparing words from the end. It increments as long as the words at the current index from the end are identical.

  4. Similarity Check: After the loops, if the sum of i and j is greater than or equal to the length of the shorter sentence (n), it means that a sufficient number of words match at both the beginning and the end, indicating similarity. The inserted sentence could be filling the gap between the matched portions. If this condition is not met, the sentences are not similar.

Time Complexity: O(L), where L is the total number of characters in both sentences. This is because the splitting, comparison, and pointer iterations all take linear time with respect to the total length.

Space Complexity: O(L), in the worst case, to store the arrays of words.

Code Implementation (Python):

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        words1, words2 = sentence1.split(), sentence2.split()
        m, n = len(words1), len(words2)
        if m < n:
            words1, words2 = words2, words1
            m, n = n, m
        i = j = 0
        while i < n and words1[i] == words2[i]:
            i += 1
        while j < n and words1[m - 1 - j] == words2[n - 1 - j]:
            j += 1
        return i + j >= n

The other language implementations (Java, C++, Go, TypeScript, JavaScript) follow the same algorithm, just with syntactic variations for each language. The key is the two-pointer approach and the condition i + j >= n which efficiently determines sentence similarity.