Problem of The Day: Sentence Similarity III

Problem Statement

Intuition

We are tasked with checking if two sentences are similar, meaning one can be converted into the other by possibly inserting words at certain places in one sentence. The intuition here is to compare the words from the end of both sentences and allow for an insertion if a mismatch occurs.

Approach

We split both sentences into individual words and use two stacks (one for each sentence) to compare them from the end. If the words at the top of both stacks match, we continue popping and comparing. If they don’t, we check whether an insertion can help us match the words, and allow only one insertion per comparison. If an insertion has already been made and we still encounter a mismatch, the sentences aren’t similar. Finally, if we exhaust both stacks and they are empty or fully aligned, we return True.

Complexity

• Time complexity: \(O(n)\), where n is the number of words in the shorter sentence. We iterate through all the words in one or both sentences once.
• Space complexity: \(O(n)\) for storing the words in stacks.

Code

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        if len(sentence1) > len(sentence2):
            return self.areSentencesSimilar(sentence2, sentence1)
        stack1 = sentence1.split()
        stack2 = sentence2.split()
        isInserted = False
        c1 = c2 = ""
        while stack1 and stack2:
            c1 = stack1.pop()
            c2 = stack2.pop()
            if c1 == c2:
                continue
            if isInserted:
                return False
            while stack2:
                isInserted = True
                c2 = stack2.pop()
                if c1 == c2:
                    if (stack1 and stack2 and stack2[-1] == stack1[-1]) or (not stack1 or not stack2):
                        break

        if not stack1 and not stack2:
            return c1 == c2
        if not stack1 and stack2 and not isInserted:
            return True
        return False

Editorial

Approach 1: Deque

class Solution:
    def areSentencesSimilar(self, s1: str, s2: str) -> bool:
        deque1 = deque(s1.split())
        deque2 = deque(s2.split())
        # Compare the prefixes or beginning of the strings.
        while deque1 and deque2 and deque1[0] == deque2[0]:
            deque1.popleft()
            deque2.popleft()
        # Compare the suffixes or ending of the strings.
        while deque1 and deque2 and deque1[-1] == deque2[-1]:
            deque1.pop()
            deque2.pop()
        return not deque1 or not deque2

• time: O(m + n)
• space: O(m + n)

Approach 2: Two Pointers

class Solution:
    def areSentencesSimilar(self, s1: str, s2: str) -> bool:
        # Split the words in sentences and store it in a string array.
        s1_words = s1.split(" ")
        s2_words = s2.split(" ")
        start, ends1, ends2 = 0, len(s1_words) - 1, len(s2_words) - 1

        # If words in s1 are more than s2, swap them and return the answer.
        if len(s1_words) > len(s2_words):
            return self.areSentencesSimilar(s2, s1)

        # Find the maximum words matching from the beginning.
        while start < len(s1_words) and s1_words[start] == s2_words[start]:
            start += 1

        # Find the maximum words matching in the end.
        while ends1 >= 0 and s1_words[ends1] == s2_words[ends2]:
            ends1 -= 1
            ends2 -= 1

        # If i reaches the end of the array, then we return true.
        return ends1 < start

• time: O(m + n)
• space: O(m + n)