给定两个字符串
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：
示例 2：
示例 3：
说明：
1 <= sentence1.length, sentence2.length <= 100
sentence1和sentence2都只包含大小写英文字母和空格。
sentence1和sentence2中的单词都只由单个空格隔开。
这题两个句子相似，当且仅当较短句子的所有单词，都能被较长句子的前缀和后缀覆盖，中间多出来的一段可以看作被插入的内容。
比如：
这两个句子相似，因为：
前缀
"hello" 匹配，后缀 "jane" 匹配。较短句子 "hello jane" 的所有单词都被覆盖了，较长句子中间多出来的 "my name is" 就可以理解为插入进去的部分。所以这题的核心是一个很具体的结构判断：
longer = prefix + inserted_middle + suffix
shorter = prefix + suffix
只要短句子的前缀部分和后缀部分能拼起来覆盖整个短句子，就返回
True。解法一：Deque —— 从两端不断弹出匹配单词
最直观的做法是把两个句子都拆成单词，然后放进双端队列。
我们先从前面开始比较。只要两个队列的队首单词相同，就同时弹出。
然后从后面开始比较。只要两个队列的队尾单词相同，也同时弹出。
如果最后其中一个队列被清空，说明较短的那个句子已经完全被前缀和后缀匹配掉了，中间剩下的部分就是另一个句子多出来的插入内容。
Deque 的写法非常贴合题意。
因为我们关心的就是：
- 开头能匹配多少；
- 结尾能匹配多少；
- 中间剩下的是否只属于其中一个句子。
如果某个句子的所有单词都被两端匹配消耗掉，那么另一个句子中间剩下的部分就可以作为插入句子。
Walk Through Example
从前面看，两个句子都以
"hello" 开头，所以弹掉 "hello"。
从后面看，两个句子都以 "jane" 结尾，所以弹掉 "jane"。
此时 sentence1 已经没有剩余单词，而 sentence2 还剩 "my name is"。
这正好表示可以往 sentence1 中间插入 "my name is"，所以返回 True。复杂度分析
设
m 和 n 分别是两个句子的字符串长度。- 时间复杂度：
O(m + n)
拆分句子需要线性时间，之后每个单词最多被弹出一次。
- 空间复杂度：
O(m + n)
因为需要把两个句子的单词存入 deque。
解法二：双指针 —— 不弹出，只记录匹配边界 （推荐）
Deque 的做法很直观，但其实我们不需要真的弹出元素。
先把两个句子拆成单词数组，然后用双指针模拟从两端匹配：
- 从左往右匹配公共前缀；
- 从右往左匹配公共后缀。
最终要判断的是：较短句子是否能被前缀匹配和后缀匹配完全覆盖。
如果前缀匹配数量加上后缀匹配数量，覆盖了整个较短句子，那么返回
True。假设：
- 较短句子是：
shorter = A B C D
- 较长句子是：
longer = A B X Y Z C D
前缀匹配到
A B，后缀匹配到 C D。较短句子的所有单词都被覆盖了，中间的 X Y Z 就是插入部分。复杂度分析
设
m 和 n 分别是两个句子的字符串长度。- 时间复杂度：
O(m + n)
拆分字符串需要线性时间，双指针匹配过程中每个单词最多被访问一次。
- 空间复杂度：
O(m + n)
因为
split() 会生成两个单词数组。如果把输入已经视为单词数组，则额外空间可以认为是
O(1)。总结
这题的关键是理解“插入任意句子”意味着什么。如果两个句子能通过插入变相等，那么：
- 较长句子一定可以写成：
prefix + inserted_middle + suffix
- 较短句子一定是：
prefix + suffix
所以我们只需要比较两端。先从开头匹配尽可能长的公共前缀，再从结尾匹配尽可能长的公共后缀。
如果较短句子的所有单词都被这两部分覆盖，就返回
True；否则返回 False。这两种方法本质完全一样。
- Deque：真的从两端删除匹配单词。
- Two Pointers：不删除，只用指针记录匹配到哪里。
Deque 写法更直观，特别适合第一次理解题意。
双指针写法更轻量。原因是它没有真实修改数据结构，只通过边界判断表达核心逻辑，代码也很短。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-1813-句子相似性-iii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 1169] 无效交易
下一篇
Production Agents Need Workflow Graphs