Leetcode Daily Question 06/10/2024 - 1813. Sentence Similarity III

Problem Description:

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.

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

Explanation:

Since we are only allowed to make 1 insertion of a sentence to make the two string equal, we need to check if the sentence of shorter length can fit into at most two groups separated by at most 1 gap in between.

We also need these groups to be at the start and/or end of the longer sentence.

For example,
s1 = "My name is Haley"
s2 = "My Haley"
This is valid because we can split s2 into two group "My", "Haley", such that they are at either end of s1 and has exactly 1 gap inbetween.

Something like:
s1 = "My name is Haley"
s2 = "My is"
is not valid. Although we can split s2 into two groups, they don't belong to either end in s1.

So we try to create these potential groups.

First, we attempt to travel from the start. When we can no longer match, we try from end of the string. We iterate both strings from the end inwards.

If the sum of the indices are longer than the shorter sentence, we know we have found the necessary conditions for a valid insertion.

def areSentencesSimilar(sentence1, sentence2):
    s1_split = sentence1.split()
    s2_split = sentence2.split()
    
    if len(s1_split) > len(s2_split):
      s1_split, s2_split = s2_split, s1_split
      
    i = 0
    while i < len(s1_split) and s1_split[i] == s2_split[i]:
      i += 1
    
    j = 0
    while j < len(s1_split) and s1_split[-1 - j] == s2_split[-1 - j]:
      j += 1
      
    return i + j >= len(s1_split)

The time complexity is O(n+m), as we traverse the sentences to create the list of words.

The space complexity is O(n+m) as we store the individual words of the sentences.

The full solution can be found near the top of the page.