题目描述

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，"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。

样例

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

输入：sentence1 = "of", sentence2 = "A lot of words"
输出：false
解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。

输入：sentence1 = "Eating right now", sentence2 = "Eating"
输出：true
解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。

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

限制

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

算法

(贪心) $O(n + m)$

1. 将两个字符串分别按照空格分隔成字符串数组。
2. 比对两个字符串的前缀和后缀，分别求出最大匹配长度 $l$ 和 $r$。
3. 如果 $l + r \ge \min{n, m}$，则结果为 $true$，因为这表示较短的字符串一定能被较长的字符串的两端所表示。

时间复杂度

• 分隔的时间复杂度为 $O(n + m)$，匹配的时间复杂度也为 $O(n + m)$，故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储分隔后的字符串数组。

C++ 代码

class Solution {
private:
    vector<string> split(const string &s) {
        const int n = s.size();
        vector<string> res;
        string t;
        for (char c : s) {
            if (c == ' ') {
                res.push_back(t);
                t.clear();
            } else {
                t.push_back(c);
            }
        }
        res.push_back(t);
        return res;
    }

public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        vector<string> s1 = split(sentence1), s2 = split(sentence2);
        const int n = s1.size(), m = s2.size();
        int l;
        for (l = 0; l < n && l < m; l++)
            if (s1[l] != s2[l])
                break;

        int r;
        for (r = 0; r < n && r < m; r++)
            if (s1[n - r - 1] != s2[m - r - 1])
                break;

        return l + r >= min(n, m);
    }
};