#1813

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Sentence Similarity III

Sentence Similarity III asks if one sentence can be transformed into another by inserting a sentence inside it.

Problem Statement

You are given two strings, sentence1 and sentence2, each representing a sentence composed of words. A sentence consists of words separated by spaces with no leading or trailing spaces. Each word contains only English letters in upper or lowercase.

Two sentences are considered similar if you can insert an arbitrary sentence (which may be empty) inside one sentence to make it identical to the other. The inserted sentence must be separated by spaces from existing words, and you need to check if one sentence can be transformed into the other.

Examples

Example 1

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

Output: true

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

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

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 Approach

Two-Pointer Scanning

Use two pointers to traverse both sentences from the beginning and end simultaneously. Start from both ends and move the pointers inward, ensuring that the words match from both directions. This approach verifies if one sentence can be a concatenation of a prefix and suffix of the other.

Prefix and Suffix Matching

The key observation is that if one sentence can become the other, then the matching words should form a continuous prefix or suffix. By checking from both ends, you can determine if there’s a valid subsequence match by inserting words between the prefix and suffix.

Handling Edge Cases

Ensure that you handle cases where one sentence is empty, or if they differ too much to ever become similar. If the length discrepancy is too large, you can immediately return false, saving computation time.

Complexity Analysis

Metric	Value
Time	O(m+n)
Space	O(m+n)

The time complexity is O(m+n), where m and n are the lengths of sentence1 and sentence2, respectively. This is because we are using two pointers to scan both sentences once. The space complexity is O(m+n) due to the space needed to store the two sentences.

What Interviewers Usually Probe

Assess if the candidate understands the two-pointer technique and its applications in string manipulation.
Look for correct handling of edge cases where one sentence is significantly shorter or longer.
Evaluate how the candidate optimizes the approach by leveraging prefixes and suffixes efficiently.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling the empty sentence case, which can lead to incorrect results when comparing with a non-empty sentence.
Forgetting to track both the prefix and suffix simultaneously, which can lead to missing valid subsequences.
Failing to account for the fact that the inserted sentence can be empty, leading to unnecessary checks in certain cases.

Follow-up variants

Modify the problem to require a minimum number of insertions and check if one sentence can become another with exactly n insertions.
Change the problem to allow insertions only at the start or end of a sentence, limiting where the subsequences can be inserted.
Extend the problem to handle multi-word subsequences, where the inserted words must form a continuous subsequence.

FAQ

What is the primary pattern used to solve Sentence Similarity III?

The problem utilizes a two-pointer scanning technique with invariant tracking to check if one sentence can be transformed into another.

How can the two-pointer technique help in solving Sentence Similarity III?

By scanning both sentences from the beginning and end, we can match prefixes and suffixes, ensuring that one sentence is a valid subsequence of the other.

What is the time complexity of Sentence Similarity III?

The time complexity is O(m+n), where m and n are the lengths of sentence1 and sentence2, respectively.

What edge cases should be considered in Sentence Similarity III?

Edge cases include empty sentences, sentences with large length discrepancies, and cases where one sentence is already a subsequence of the other.

How does GhostInterview help with common pitfalls in this problem?

GhostInterview helps by emphasizing efficient edge case handling and guiding you through the two-pointer technique to avoid common mistakes like failing to track both prefixes and suffixes simultaneously.

terminal

Solution

Solution 1: Two Pointers

We split the two sentences into two word arrays `words1` and `words2` by spaces. Let the lengths of `words1` and `words2` be $m$ and $n$, respectively, and assume that $m \ge nn.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#1898 maximum number of removable characters #1961 check if string is a prefix of array #2108 find first palindromic string in the array