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
- Let
abe the shorter word list andbthe longer. The question is whetherais a prefix followed by a suffix ofb, with the middle ofbinserted. - Match as long a prefix as possible between
aandb. - Then match as long a suffix as possible, without overlapping the already-matched prefix.
- 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) - ito 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
ais 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.