题目描述
给你一个下标从 0 开始的字符串 str1
和 str2
。
一次操作中,你选择 str1
中的若干下标。对于选中的每一个下标 i
,你将 str1[i]
循环 递增,变成下一个字符。也就是说 'a'
变成 'b'
,'b'
变成 'c'
,以此类推,'z'
变成 'a'
。
如果执行以上操作 至多一次,可以让 str2
成为 str1
的子序列,请你返回 true
,否则返回 false
。
注意:一个字符串的子序列指的是从原字符串中删除一些(可以一个字符也不删)字符后,剩下字符按照原本先后顺序组成的新字符串。
样例
输入:str1 = "abc", str2 = "ad"
输出:true
解释:选择 str1 中的下标 2。
将 str1[2] 循环递增,得到 'd'。
因此,str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true。
输入:str1 = "zc", str2 = "ad"
输出:true
解释:选择 str1 中的下标 0 和 1。
将 str1[0] 循环递增得到 'a'。
将 str1[1] 循环递增得到 'd'。
因此,str1 变成 "ad" 且 str2 现在是一个子序列。所以返回 true。
输入:str1 = "ab", str2 = "d"
输出:false
解释:这个例子中,没法在执行一次操作的前提下,将 str2 变为 str1 的子序列。
所以返回 false。
限制
1 <= str1.length <= 10^5
1 <= str2.length <= 10^5
str1
和str2
只包含小写英文字母。
算法
(双指针) $O(n + m)$
- 使用双指针寻找
str2[i]
的匹配str1[j]
,如果str2[i]
和str1[j]
相同,或者前者比后者大 $1$,则视为相同。 - 如果中途 $j$ 达到了 $n$ 没有找到匹配,则返回失败。
时间复杂度
- 遍历两个字符串各一次,故时间复杂度为 $O(n + m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
bool valid(char a, char b) {
return a == b || a == (b - 'a' + 1) % 26 + 'a';
}
public:
bool canMakeSubsequence(string str1, string str2) {
const int n = str1.size(), m = str2.size();
if (n < m)
return false;
for (int i = 0, j = 0; i < m; i++) {
while (j < n && !valid(str2[i], str1[j]))
j++;
if (j == n)
return false;
j++;
}
return true;
}
};