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.

#1813

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

句子相似性 III

给定两个字符串 sentence1 和 sentence2 ，每个表示由一些单词组成的一个句子。句子是一系列由单个空格分隔的单词，且开头和结尾没有多余空格。每个单词都只包含大写和小写英文字母。如果两个句子 s1 和 s2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一…

数组双指针字符串

题目描述

给定两个字符串 sentence1 和 sentence2，每个表示由一些单词组成的一个句子。句子是一系列由单个空格分隔的单词，且开头和结尾没有多余空格。每个单词都只包含大写和小写英文字母。

如果两个句子 s1 和 s2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。注意，插入的句子必须与现有单词用空白隔开。

比方说，

s1 = "Hello Jane" 与 s2 = "Hello my name is Jane"，我们可以往 s1 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 s2 。
s1 = "Frog cool" 与 s2 = "Frogs are cool" 不是相似的，因为尽管往 s1 中插入 "s are"，它没有与 "Frog" 用空格隔开。

给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是相似的，请你返回 true ，否则返回 false 。

示例 1：

输入：sentence1 = "My name is Haley", sentence2 = "My Haley"

输出：true

解释：可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ，得到 sentence1 。

示例 2：

输入：sentence1 = "of", sentence2 = "A lot of words"

输出：false

解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。

示例 3：

输入：sentence1 = "Eating right now", sentence2 = "Eating"

输出：true

解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。

提示：

1 <= sentence1.length, sentence2.length <= 100
sentence1 和 sentence2 都只包含大小写英文字母和空格。
sentence1 和 sentence2 中的单词都只由单个空格隔开。

lightbulb

解题思路

方法一：双指针

我们将两个句子按照空格分割成两个单词数组 words1 和 words2，假设 words1 和 words2 的长度分别为 $m$ 和 $n$ ，不妨设 $m \geq n$ 。

我们使用双指针 $i$ 和 $j$ ，初始时 $i = j = 0$ 。接下来，我们循环判断 words1[i] 是否等于 words2[i]，是则指针 $i$ 继续右移；然后我们循环判断 words1[m - 1 - j] 是否等于 words2[n - 1 - j]，是则指针 $j$ 继续右移。

循环结束后，如果 $i + j \geq n$ ，说明两个句子相似，返回 true，否则返回 false。

时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ 。其中 $L$ 为两个句子的长度之和。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	O(m+n)
空间	O(m+n)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1898 可移除字符的最大数目 #1961 检查字符串是否为数组前缀 #2108 找出数组中的第一个回文字符串