Medium

题目描述

给定两个字符串 sentence1 和 sentence2，每个字符串都表示由单词组成的句子。句子是由单个空格分隔且没有前导或尾随空格的单词列表。每个单词仅由大写和小写英文字母组成。

如果可以在其中一个句子中插入任意句子（可能为空），使两个句子变得相等，则认为两个句子 s1 和 s2 是相似的。注意，插入的句子必须用空格与现有单词分隔。

例如：

  • s1 = "Hello Jane" 和 s2 = "Hello my name is Jane" 可以通过在 s1 的 “Hello” 和 “Jane” 之间插入 “my name is” 使其相等。
  • s1 = "Frog cool" 和 s2 = "Frogs are cool" 不相似，因为虽然有句子 “s are” 插入到 s1 中，但它没有用空格与 “Frog” 分隔。

给定两个句子 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 中的单词由单个空格分隔

解题思路

解题思路

这道题的核心思想是：如果两个句子相似，那么其中一个句子可以看作是另一个句子的前缀和后缀的拼接。

具体分析：

  1. 将两个句子按空格分割成单词数组
  2. 使用双指针技术，分别从前往后和从后往前匹配相同的单词
  3. 从前往后找最长公共前缀：比较两个数组开头的单词，直到遇到不同的单词为止
  4. 从后往前找最长公共后缀：比较两个数组末尾的单词，直到遇到不同的单词为止
  5. 如果前缀长度 + 后缀长度 >= 较短句子的单词数量，说明较短的句子可以完全由较长句子的前缀和后缀组成

关键观察：两个句子相似的充要条件是，较短的句子是较长句子去掉中间某一段连续单词后的结果。

算法步骤：

  • 确保 sentence1 是较短的句子（便于处理）
  • 用双指针 left 和 right 分别从两端匹配
  • 当 left + right >= len(words1) 时，说明 words1 可以被 words2 的前缀和后缀完全覆盖

代码实现

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        vector<string> words1 = split(sentence1);
        vector<string> words2 = split(sentence2);
        
        if (words1.size() > words2.size()) {
            swap(words1, words2);
        }
        
        int left = 0, right = 0;
        int n1 = words1.size(), n2 = words2.size();
        
        // 从前往后匹配
        while (left < n1 && words1[left] == words2[left]) {
            left++;
        }
        
        // 从后往前匹配
        while (right < n1 && words1[n1 - 1 - right] == words2[n2 - 1 - right]) {
            right++;
        }
        
        return left + right >= n1;
    }
    
private:
    vector<string> split(const string& sentence) {
        vector<string> words;
        stringstream ss(sentence);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }
        return words;
    }
};

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        words1 = sentence1.split()
        words2 = sentence2.split()
        
        if len(words1) > len(words2):
            words1, words2 = words2, words1
        
        left = 0
        right = 0
        n1, n2 = len(words1), len(words2)
        
        # 从前往后匹配
        while left < n1 and words1[left] == words2[left]:
            left += 1
        
        # 从后往前匹配
        while right < n1 and words1[n1 - 1 - right] == words2[n2 - 1 - right]:
            right += 1
        
        return left + right >= n1

public class Solution {
    public bool AreSentencesSimilar(string sentence1, string sentence2) {
        string[] words1 = sentence1.Split(' ');
        string[] words2 = sentence2.Split(' ');
        
        if (words1.Length > words2.Length) {
            (words1, words2) = (words2, words1);
        }
        
        int left = 0, right = 0;
        int n1 = words1.Length, n2 = words2.Length;
        
        // 从前往后匹配
        while (left < n1 && words1[left] == words2[left]) {
            left++;
        }
        
        // 从后往前匹配
        while (right < n1 && words1[n1 - 1 - right] == words2[n2 - 1 - right]) {
            right++;
        }
        
        return left + right >= n1;
    }
}

var areSentencesSimilar = function(sentence1, sentence2) {
    const words1 = sentence1.split(' ');
    const words2 = sentence2.split(' ');
    
    if (words1.length > words2.length) {
        return areSentencesSimilar(sentence2, sentence1);
    }
    
    let left = 0, right = 0;
    const n1 = words1.length, n2 = words2.length;
    
    // 从前往后匹配
    while (left < n1 && words1[left]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n + m)
空间复杂度O(n + m)

其中 n 和 m 分别是两个句子中单词的数量。时间复杂度主要来自分割字符串和双指针遍历，空间复杂度来自存储分割后的单词数组。