2825. 循环增长使字符串子序列等于另一个字符串

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

题目

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to makestr2 a subsequence ofstr1 by performing the operationat most once , and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"

Output: true

Explanation: Select index 2 in str1.

Increment str1[2] to become 'd'.

Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"

Output: true

Explanation: Select indices 0 and 1 in str1.

Increment str1[0] to become 'a'.

Increment str1[1] to become 'd'.

Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"

Output: false

Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once.

Therefore, false is returned.

Constraints:

• 1 <= str1.length <= 10^5
• 1 <= str2.length <= 10^5
• str1 and str2 consist of only lowercase English letters.

题目大意

给你一个下标从 0 开始的字符串 str1 和 str2 。

一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环 递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。

如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。

注意： 一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。

示例 1：

输入： str1 = "abc", str2 = "ad"

输出： true

解释： 选择 str1 中的下标 2 。

将 str1[2] 循环递增，得到 'd' 。

因此，str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true 。

示例 2：

输入： str1 = "zc", str2 = "ad"

输出： true

解释： 选择 str1 中的下标 0 和 1 。

将 str1[0] 循环递增得到 'a' 。

将 str1[1] 循环递增得到 'd' 。

因此，str1 变成 "ad" 且 str2 现在是一个子序列。所以返回 true 。

示例 3：

输入： str1 = "ab", str2 = "d"

输出： false

解释： 这个例子中，没法在执行一次操作的前提下，将 str2 变为 str1 的子序列。

所以返回 false 。

提示：

• 1 <= str1.length <= 10^5
• 1 <= str2.length <= 10^5
• str1 和 str2 只包含小写英文字母。

解题思路

字符比较规则

对于 str1[i] 和 str2[j]，如果：

• str1[i] == str2[j]，匹配成功。
• (str1[i] + 1) % 26 == str2[j]，表示 str1[i] 通过一次循环递增可以变成 str2[j]。

双指针法

• 指针 prev1 遍历 str1。
• 指针 prev2 遍历 str2。
• 每次当 str1[prev1] 满足上述匹配规则时，将 prev2 向前移动一位，表示 str2[prev2] 找到了对应的字符。
• 如果最后 prev2 能遍历完 str2，则说明 str2 是 str1 的子序列。

算法步骤

1. 初始化指针 prev1 和 prev2 均为 0。
2. 遍历 str1，对当前字符进行判断：
   • 如果 str1[prev1] 与 str2[prev2] 匹配，移动 prev2。
   • 无论是否匹配，指针 prev1 总是向右移动。
3. 检查 prev2 是否等于 str2.length，如果是，则返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n = str1.length，每个字符最多遍历一次。
• 空间复杂度：O(1)，使用了固定数量的变量。

代码

/**
 * @param {string} str1
 * @param {string} str2
 * @return {boolean}
 */
var canMakeSubsequence = function (str1, str2) {
	let prev1 = 0,
		prev2 = 0;
	while (prev1 < str1.length && prev2 < str2.length) {
		if (
			str1[prev1] == str2[prev2] ||
			(str1.charCodeAt(prev1) + 1 - str2.charCodeAt(prev2)) % 26 == 0
		) {
			prev2++;
		}
		prev1++;
	}
	return prev2 == str2.length;
};

相关题目

题号	标题	题解	标签	难度	力扣
392	判断子序列	[✓]	双指针 字符串 动态规划	🟢	🀄️ 🔗