力扣1813-句子相似性3

摘要: 双串单向双指针

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个双指针的问题，力扣 1813。本题比较纯粹，就是双串单向双指针，没有综合其他的算法。

双串单向双指针是双指针中的一种重要的类型，它的做法是这样的：如果两个串的长度分别为 n1 和 n2，那么对两个串分别维护指针 i1 和 i2，两个指针都从 0 开始，按照问题的要求推进指针并维护答案，直至结束。这种思路可以解决很多问题，例如字符串精确匹配的暴力算法、子序列匹配的贪心算法，都是双串单向双指针算法。

---

题目

• 1813. 句子相似性 III

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，”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.length, sentence2.length <= 100
sentence1 和 sentence2 都只包含大小写英文字母和空格。
sentence1 和 sentence2 中的单词都只由单个空格隔开。

示例 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

题解

算法: 双指针

两个串 s1, s2 的长度分别为 n1, n2，不妨设 n1 < n2。我们要判断的是能不能在 s1 中插入一个句子形成 s2。

假设插入位置是 p，有以下三种情况：

(1) 如果 p = 0，那么 s1 必须是 s2 的后缀；
(2) 如果 p = n1，那么 s1 必须是 s2 的前缀；
(3) 如果 0 < p < n1，则 s1[0..p-1] 需要是 s2 的前缀且 s1[p..n1-1] 需要是 s2 的后缀。

将以上三种情况综合起来，如果位置 p 要满足要求，需要 s1 与 s2 形成公共前缀 s1[0..p-1]，与公共后缀 s2[p..n1-1]。其中 (1) 种情况公共前缀是空串，第 (2) 种情况公共后缀是空串。

因此我们可以先匹配公共前缀 s1[0..l]，然后匹配公共后缀 s1[r1..n1-1]，如果 l + 1 = r1 则满足要求。

在匹配前缀的过程是用到双串单向双指针的地方，对两个串分别维护两个指针，只要两个指针对应的字符相等，就同时推进两个指针，直至结束。匹配后缀的过程类似。

代码 (C++)

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        vector<string> words1, words2;
        get_word(sentence1, words1);
        get_word(sentence2, words2);
        return check(words1, words2);
    }

private:
    bool check(const vector<string>& words1, const vector<string>& words2)
    {
        int n1 = words1.size(), n2 = words2.size();
        if(n1 > n2)
            return check(words2, words1);
        int l = 0;
        while(l < n1 && words1[l] == words2[l])
            ++l;
        int r1 = n1 - 1, r2 = n2 - 1;
        while(r1 >= l && words1[r1] == words2[r2])
        {
            --r1;
            --r2;
        }
        return r1 < l;
    }

    void get_word(const string& sentence, vector<string>& words)
    {
        int n = sentence.size();
        int i = 0;
        while(i < n)
        {
            int j = i;
            while(j < n && sentence[j] == ' ')
                ++j;
            if(j == n)
                break;
            i = j;
            while(j < n && sentence[j] != ' ')
                ++j;
            words.emplace_back(sentence.substr(i, j - i));
            i = j;
        }
    }
};

代码 (Python)

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        def check(words1, words2):
            n1 = len(words1)
            n2 = len(words2)
            if n1 > n2:
                return check(words2, words1)
            # n1 <= n2
            l = 0
            while l < n1 and words1[l] == words2[l]:
                l += 1
            r1 = n1 - 1
            r2 = n2 - 1
            while r1 >= l and words1[r1] == words2[r2]:
                r1 -= 1
                r2 -= 1
            return r1 < l

        words1 = sentence1.split(" ")
        words2 = sentence2.split(" ")
        return check(words1, words2)

---