⚡Flashcard Drill➔
NeetCode #213LC-1813MediumTwo Pointers
← Back to All Problems

#213 · #1813 · Sentence Similarity III(句子相似性 III)

📌 Problem Statement & Constraints

A sentence is similar to another if you can insert an arbitrary sentence (possibly empty) inside one of them to make them equal. Given two sentences as strings, return whether they are similar. Constraints: 1 <= sentence1.length, sentence2.length <= 100; words are separated by single spaces.

💡 Core Algorithmic Approaches

  1. Let a be the shorter word list and b the longer. The question is whether a is a prefix followed by a suffix of b, with the middle of b inserted.
  2. Match as long a prefix as possible between a and b.
  3. Then match as long a suffix as possible, without overlapping the already-matched prefix.
  4. The sentences are similar exactly when the prefix length plus the suffix length covers all of a.

💻 Benchmark Python3 Implementation

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        a, b = sentence1.split(), sentence2.split()
        if len(a) > len(b):
            a, b = b, a                # a is the shorter list
        i = 0
        while i < len(a) and a[i] == b[i]:
            i += 1                     # matched prefix length
        j = 0
        while j < len(a) - i and a[len(a) - 1 - j] == b[len(b) - 1 - j]:
            j += 1                     # matched suffix length, not overlapping the prefix
        return i + j == len(a)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): the splits plus two linear scans.
💾 Space Complexity
O(m + n) for the word lists.

⚠️ Interview Pitfalls & Follow-ups

  • Allowing the prefix and suffix to overlap: the suffix scan must stop at len(a) - i to avoid double-counting words.
  • Only checking the prefix: the insertion can be in the middle, so both ends must be matched.
  • Comparing the raw strings instead of the word lists: "ab cd" and "ab cd" are equal as strings, but the similarity definition operates on words.
  • Forgetting to normalise which sentence is shorter: the algorithm assumes a is the shorter one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems