1813. 句子相似性 III

🟠   🔖  数组 双指针 字符串  🔗 力扣 LeetCode

题目

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true ifsentence1andsentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"

Output: true

Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"

Output: false

Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"

Output: true

Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Constraints:

• 1 <= sentence1.length, sentence2.length <= 100
• sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
• The words in sentence1 and sentence2 are separated by a single space.

题目大意

给定两个字符串 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. 初始化：首先将 sentence1 和 sentence2 按空格拆分为单词数组 arr1 和 arr2。
2. 双指针匹配前缀：使用指针 i 从头开始比较 arr1 和 arr2，找到从头部匹配的最大长度。
3. 双指针匹配后缀：使用指针 j 从尾部开始比较 arr1 和 arr2，找到从尾部匹配的最大长度。
4. 判断：如果前缀和后缀加起来的长度能够覆盖 arr2 中的全部元素，或者 arr1 中的全部元素（即中间部分可以删除），则返回 true，否则返回 false。

复杂度分析

• 时间复杂度：O(min(n, m))，其中 n 是 sentence1 中单词的数量，m 是 sentence2 中单词的数量。我们最多遍历两者中较短的句子的所有单词。
• 空间复杂度：O(n + m)，我们需要额外的空间来存储 sentence1 和 sentence2 的单词数组。

代码

/**
 * @param {string} sentence1
 * @param {string} sentence2
 * @return {boolean}
 */
var areSentencesSimilar = function (sentence1, sentence2) {
	const arr1 = sentence1.split(' '),
		arr2 = sentence2.split(' '),
		len1 = arr1.length,
		len2 = arr2.length;

	let i = 0,
		j = 0;

	// 从头部开始匹配前缀
	while (i < len1 && i < len2 && arr1[i] == arr2[i]) {
		i++;
	}

	// 从尾部开始匹配后缀
	while (
		j < len1 - i &&
		j < len2 - i &&
		arr1[len1 - 1 - j] == arr2[len2 - 1 - j]
	) {
		j++;
	}

	// 如果匹配的前缀和后缀长度加起来能够覆盖较短句子的所有元素，则相似
	return i + j >= Math.min(len1, len2);
};