LeetCode 1813 - Sentence Similarity III

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, String

Solution

Problem Understanding

The problem is asking us to determine whether two sentences can be made identical by inserting a contiguous sequence of words (possibly empty) into one of them. Each sentence is a string of words separated by single spaces. Importantly, the insertion must occur between words, not by altering any existing word.

The input consists of two strings, sentence1 and sentence2. The expected output is a boolean: true if the sentences can be made identical by inserting a sentence into one of them, and false otherwise.

Key points to note are that both sentences contain only English letters and spaces, words are separated by single spaces, and the length of each sentence is capped at 100 characters. This means we can use an approach that is linear in the number of words without worrying about performance issues.

Important edge cases include:

One sentence is fully contained at the start or end of the other (e.g., "Eating" vs "Eating right now").
Sentences have no matching prefix or suffix.
Sentences with a single word.
Sentences that differ by a single word in the middle.

Approaches

The brute-force approach would attempt every possible contiguous substring insertion from one sentence into the other and compare the resulting sentence to see if it matches. This would require O(n² * m) time where n and m are the number of words in the sentences, which is unnecessary and inefficient.

The key observation for an optimal solution is that the sentences must share a common prefix and/or suffix. If we strip matching words from the start and end, whatever remains in the longer sentence can be considered the "inserted sentence." If the remaining middle of the shorter sentence is empty, the sentences are similar. This can be efficiently implemented using a two-pointer approach: one pointer starts at the beginning of both word lists and advances while words match, and another pointer starts at the end and moves backward while words match.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² * m)	O(n + m)	Try inserting every contiguous substring and compare
Optimal	O(n + m)	O(n + m)	Two-pointer approach using prefix and suffix matching

Algorithm Walkthrough

Split both sentences into lists of words. Let words1 and words2 represent the two sentences. This allows easy indexing and comparison.
Initialize two pointers, i starting at 0 for prefix comparison, and j starting at the last indices of both lists for suffix comparison.
Move pointer i forward as long as words1[i] == words2[i] and neither pointer has reached the end. This identifies the common prefix.
Move pointer j backward as long as words1[end1 - j] == words2[end2 - j] and the remaining words do not overlap with the prefix pointer. This identifies the common suffix.
After advancing both pointers, check if the prefix and suffix cover the shorter sentence completely. If yes, the sentences are similar; otherwise, they are not.

Why it works: The algorithm guarantees that all words at the start and end that can match are matched. If the entire shorter sentence is matched by prefix and suffix, the leftover words in the longer sentence represent the possible inserted sentence. No other insertion can make them equal.

Python Solution

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

The implementation first splits the sentences into word lists. To simplify handling, we always treat words1 as the shorter sentence. The prefix pointer i moves forward while words match. The suffix pointer j moves backward, ensuring it does not overlap with the prefix. Finally, we check if all words in the shorter sentence have been matched; if so, a contiguous insertion could make the sentences equal.

Go Solution

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
    words1 := strings.Fields(sentence1)
    words2 := strings.Fields(sentence2)
    
    if len(words1) > len(words2) {
        words1, words2 = words2, words1
    }
    
    i := 0
    for i < len(words1) && words1[i] == words2[i] {
        i++
    }
    
    j := 0
    for j < len(words1) - i && words1[len(words1)-1-j] == words2[len(words2)-1-j] {
        j++
    }
    
    return i + j == len(words1)
}

The Go implementation mirrors the Python version, using strings.Fields to split sentences into words. Go requires care with slice indexing, especially for suffix comparison. The logic otherwise remains identical.

Worked Examples

Example 1: sentence1 = "My name is Haley", sentence2 = "My Haley"

Step	i	j	Matched Prefix	Matched Suffix	Remaining words in shorter sentence
Initial	0	0			words1=["My","name","is","Haley"]
Prefix match	1	0	"My"		"name","is","Haley"
Suffix match	1	1	"My"	"Haley"	"name","is"
i + j == len(words1)?	1+1=2	4	No		True

Example 2: sentence1 = "of", sentence2 = "A lot of words"

Step	Prefix	Suffix	Remaining
Prefix	""		"of"
Suffix	""	""	"of"
i + j == len(words1)?			False

Example 3: sentence1 = "Eating right now", sentence2 = "Eating"

Step	i	j	Prefix	Remaining
Prefix	1	0	"Eating"	"right","now"
Suffix	1	0	"Eating"	"right","now"
i + j == len(words2)?	1 + 0 == 1	True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Split sentences into words and compare prefix/suffix linearly
Space	O(n + m)	Store words in lists for both sentences

The linear time complexity is acceptable because the sentences are at most 100 characters long, resulting in a small number of words.

Test Cases

# Provided examples
assert Solution().areSentencesSimilar("My name is Haley", "My Haley") == True  # middle insertion
assert Solution().areSentencesSimilar("of", "A lot of words") == False        # no match
assert Solution().areSentencesSimilar("Eating right now", "Eating") == True   # end insertion

# Edge cases
assert Solution().areSentencesSimilar("Hello", "Hello") == True                 # identical
assert Solution().areSentencesSimilar("Hello", "Hello World") == True           # end insertion
assert Solution().areSentencesSimilar("World Hello", "Hello") == False          # unmatched prefix
assert Solution().areSentencesSimilar("A B C", "A X B C") == False              # insertion not contiguous
assert Solution().areSentencesSimilar("A B C", "X A B C") == True               # start insertion
assert Solution().areSentencesSimilar("A B C", "A B C X") == True               # end insertion

Test	Why
"My name is Haley" vs "My Haley"	Middle insertion, should be true
"of" vs "A lot of words"	No match possible, should be false
"Eating right now" vs "Eating"	End insertion, should be true
"Hello" vs "Hello"	Identical sentences, trivial case
"Hello" vs "Hello World"	End insertion, should be true
"World Hello" vs "Hello"	Prefix does not match, should be false
"A B C" vs "A X B C"	Non-contiguous insertion not allowed
"A B C" vs "X A B C"	Start insertion, valid
"A B C" vs "A B C X"	End insertion, valid

Edge Cases

Single word sentences: If either sentence contains a single word, the algorithm