句子相似性 III

标签: 数组 双指针 字符串

难度: Medium

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，"Hello World" ，"HELLO" ，"hello world hello world" 都是句子。每个单词都 只 包含大写和小写英文字母。

如果两个句子 sentence1 和 sentence2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。比方说，sentence1 = "Hello my name is Jane" 且 sentence2 = "Hello Jane" ，我们可以往 sentence2 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 sentence1 。

给你两个句子 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 。

示例 4：

输入：sentence1 = "Luky", sentence2 = "Lucccky"
输出：false

 

提示：

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

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        if len(sentence1) > len(sentence2): 
            return self.areSentencesSimilar(sentence2, sentence1) 
        a, b = sentence1.split(), sentence2.split() 
        i, j, k = 0, len(a) - 1, 0  
        while i < len(a) and k < len(b): 
            if a[i] == b[k]: 
                i += 1 
                k += 1 
            else:
                break
        k = len(b) - 1 
        while j >= 0 and k >= 0: 
            if a[j] == b[k]: 
                j -= 1 
                k -= 1 
            else:
                break 
        return i > j

Explain

该题解的核心思路是通过检查两个句子的开头和结尾是否可以匹配来判断他们是否相似。首先，确保sentence1是较短的句子，如果不是，则递归调用函数交换两个句子的位置。接着，将两个句子分割成单词数组。使用两个指针i和k分别从句子的开始比较单词是否相同，若相同则同时向后移动。当遇到不同的单词时停止。然后，使用两个指针j和k从两个句子的末尾开始向前比较，若相同则同时向前移动。最后，若i大于j，则说明所有能匹配的单词都已匹配完毕，且中间的部分可以由插入得到，返回true，否则返回false。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        if len(sentence1) > len(sentence2): 
            return self.areSentencesSimilar(sentence2, sentence1)  # 确保sentence1是较短的句子
        a, b = sentence1.split(), sentence2.split()  # 分割句子为单词数组
        i, j, k = 0, len(a) - 1, 0  
        while i < len(a) and k < len(b):  # 从前向后比较
            if a[i] == b[k]: 
                i += 1 
                k += 1 
            else:
                break
        k = len(b) - 1 
        while j >= 0 and k >= 0:  # 从后向前比较
            if a[j] == b[k]: 
                j -= 1 
                k -= 1 
            else:
                break 
        return i > j  # 如果i > j，表示可以通过插入得到另一个句子

Explore

首先确保sentence1是较短的句子，是为了简化代码逻辑，因为算法的目的是检查一个较长的句子是否可以通过插入方式得到较短的句子。如果sentence1是较长的，通过递归调用函数并交换两个句子的位置，可以统一处理逻辑，使得总是检查较短句子是否可以由较长的句子通过插入得到。这样做不影响算法的正确性，反而使得实现更加统一和简洁。

在这种情况下，算法将返回false。因为算法通过从前向后和从后向前检查单词是否相同，如果单词顺序不同，则无法在句子的开头或结尾找到完全匹配的单词序列。例如在给定的例子中，从前向后和从后向前比较都会在第一个比较时遇到不同的单词，因此i和j的条件（i > j）无法满足，所以返回false。

在算法中，指针i和j用于比较两个句子中的单词是否相同。指针i从0开始，向后移动，直到达到数组a的长度或遇到不同的单词停止。指针j从数组a的最后一个元素开始，向前移动，直到索引小于0或遇到不同的单词停止。指针i和j的作用在于识别两个句子中相同的前缀和后缀，如果在i和j的指示范围之外的句子b的部分可以插入到句子a中，以形成句子b，那么算法返回true。i > j的条件检查是否所有a中的单词都已经在b中按顺序找到了对应的位置。

之所以从len(b) - 1开始而不是从len(a) - 1开始，是因为算法需要检查句子b是否可以通过插入一些单词到句子a中来形成。由于句子b可能比句子a长，从b的末尾开始比较可以确保我们考虑到b中所有的单词。如果我们从len(a) - 1开始，那么当b比a长时，我们将无法比较b中超出a长度的部分，这可能会错过一些可以通过插入得到的正确匹配。