Sentence Similarity III: Two-Pointer Word Matching

LeetCode 1813, Sentence Similarity III, asks whether one sentence can become the other by inserting a sequence of words into it. Two sentences are "similar" if you can take the shorter one and plug in a contiguous block of words somewhere (at the beginning, in the middle, or at the end) to produce the longer one.

For example:

• sentence1 = "My name is Haley" and sentence2 = "My Haley" returns True. You can insert "name is" into the middle of sentence2 to get sentence1.
• sentence1 = "of" and sentence2 = "A lot of words" returns True. Sentence1 matches the end of sentence2. Inserting "A lot of" at the start of sentence1 gives sentence2.
• sentence1 = "Eating right now" and sentence2 = "Eating" returns True. Inserting "right now" at the end of sentence2 gives sentence1.
• sentence1 = "Luky" and sentence2 = "Lucccky" returns False. These are individual words that differ, and similarity is defined at the word level, not the character level.

The key insight is that if one sentence can become the other by insertion, then the words at the beginning of both sentences must match up to some point, and the words at the end must match up to some point. The unmatched words in the longer sentence form the inserted block.

The approach: two pointers from both ends

Split both sentences into word arrays. Make sure you know which array is shorter. Then use two counters:

1. Left pointer: start at index 0 and walk forward while the words match.
2. Right pointer: start at the last index of each array and walk backward while the words match.

If the left and right matches together cover every word in the shorter array, the answer is True. The remaining unmatched words in the longer array are the "inserted" portion.

Why does this work? If one sentence is formed by inserting words into the other, the shared words must form a prefix and a suffix of both sentences. There is no way for matching words to appear in the middle with mismatches on both sides. The insertion point splits the shorter sentence into a prefix part and a suffix part that align with the beginning and end of the longer sentence.

The code

def are_sentences_similar(sentence1: str, sentence2: str) -> bool:
    words1 = sentence1.split()
    words2 = sentence2.split()
    if len(words1) > len(words2):
        words1, words2 = words2, words1
    left = 0
    while left < len(words1) and words1[left] == words2[left]:
        left += 1
    right = 0
    while right < len(words1) - left and words1[len(words1) - 1 - right] == words2[len(words2) - 1 - right]:
        right += 1
    return left + right >= len(words1)

The swap at the top guarantees words1 is the shorter (or equal-length) array. The left loop matches as many words as possible from the front. The right loop matches from the back, but only for the words not already claimed by the left pointer (len(words1) - left remaining). Finally, if every word in the shorter array was matched by either the left or right pointer, the sentences are similar.

Visual walkthrough

Let's trace the algorithm on sentence1 = "My name is Haley" and sentence2 = "My Haley".

The left pointer matched one word from the front ("My"). The right pointer matched one word from the back ("Haley"). Together, 1 + 1 = 2, which covers the entire shorter array of length 2. The unmatched words "name" and "is" in the longer array are the inserted portion.

Complexity analysis

The left and right pointers each visit every word at most once. Splitting the sentences into arrays takes O(n) time and space. There is no nested loop.

Building blocks

This problem combines two patterns that you will see in many string and array problems.

Prefix-suffix matching

The core idea is that two sequences share a common prefix and a common suffix. You match from the left until the words diverge, then match from the right until the words diverge. Whatever is left in the middle is the "gap." This same pattern appears in problems involving edit operations, diff algorithms, and version comparison.

Two-pointer convergence on sorted or ordered data

Even though this problem does not involve sorting, the word arrays have a fixed order (the order of words in the sentence). The two pointers start at opposite ends of the arrays and walk inward. This is the same shape as the classic two-pointer technique used in problems like Valid Palindrome, Two Sum II, and container problems. The difference here is that you are comparing across two arrays rather than within one.

Edge cases

• Identical sentences. If both sentences are the same, every word matches from the left. left equals the length of both arrays. left + right covers everything. Returns True.
• One sentence is a prefix of the other. For example, "Hello" and "Hello Jane". The left pointer matches "Hello", covering the entire shorter array. right stays at 0. 1 + 0 = 1, which equals len(words1). Returns True.
• One sentence is a suffix of the other. For example, "world" and "Hello world". The left pointer finds no match at index 0 ("world" vs "Hello"). The right pointer matches "world" from the back. 0 + 1 = 1. Returns True.
• No overlap at all. For example, "Hello" and "World". Left matches nothing. Right matches nothing. 0 + 0 = 0, which is less than 1. Returns False.

From understanding to recall

You can follow this solution step by step right now. But the details that trip people up in an interview are the ones that fade first: swapping to ensure words1 is shorter, the len(words1) - left bound on the right loop, and the final left + right >= len(words1) check. These are small, precise conditions that are easy to get wrong if you have not practiced them recently.

Spaced repetition targets exactly these details. Instead of re-reading the entire solution, you drill the prefix-suffix matching pattern at increasing intervals. After a few reps, the swap logic and pointer bounds become automatic. When you see a sentence or string comparison problem in an interview, you are not reconstructing the solution from scratch. You are recalling a pattern you have already internalized.

Related posts

• Valid Palindrome - A two-pointer string problem that also compares from both ends
• Longest Common Prefix - A string problem built on prefix matching across multiple strings
• Find the Index of the First Occurrence in a String - Another string matching problem using a sliding comparison technique