Medium

题目描述

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

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

如果通过 最多一次 操作可以使 str2 成为 str1 的子序列，则返回 true，否则返回 false。

注意： 字符串的子序列是通过删除原字符串中的一些（可能为零）字符而形成的新字符串，且不改变其余字符的相对位置。

示例 1：

输入：str1 = "abc", str2 = "ad"
输出：true
解释：选择下标 2。
将 str1[2] 递增变成 'd'。
因此，str1 变成 "abd"，str2 现在是一个子序列。所以返回 true。

示例 2：

输入：str1 = "zc", str2 = "ad"
输出：true
解释：选择下标 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⁵
  • 1 <= str2.length <= 10⁵
  • str1 和 str2 仅由小写英文字母组成。

解题思路

解题思路

这道题本质上是一个子序列匹配问题，但有个特殊条件：我们可以对 str1 中的任意字符进行一次循环递增操作。

核心观察

对于 str1 中的每个字符，它可以匹配 str2 中的字符有两种情况：

  1. 字符本身就相等
  2. 字符经过一次循环递增后相等（如 ‘a’ 可以变成 ‘b’，‘z’ 可以变成 ‘a’）

算法步骤

使用双指针技术：

  • i 指向 str1 的当前位置
  • j 指向 str2 的当前位置

对于每个 str1[i]，检查它是否能匹配 str2[j]：

  • 如果 str1[i] == str2[j] 或者 str1[i] 经过一次递增等于 str2[j]，则两个指针都前移
  • 否则只有 i 前移

最终如果 j 到达了 str2 的末尾，说明 str2 的所有字符都找到了匹配。

循环递增的实现

字符 c 经过一次递增后变成 ((c - 'a' + 1) % 26) + 'a'，这样 ‘z’ 会正确变成 ‘a’。

代码实现

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int i = 0, j = 0;
        int n1 = str1.length(), n2 = str2.length();
        
        while (i < n1 && j < n2) {
            char original = str1[i];
            char incremented = ((str1[i] - 'a' + 1) % 26) + 'a';
            
            if (original == str2[j] || incremented == str2[j]) {
                j++;
            }
            i++;
        }
        
        return j == n2;
    }
};

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i = j = 0
        n1, n2 = len(str1), len(str2)
        
        while i < n1 and j < n2:
            original = str1[i]
            incremented = chr((ord(str1[i]) - ord('a') + 1) % 26 + ord('a'))
            
            if original == str2[j] or incremented == str2[j]:
                j += 1
            i += 1
        
        return j == n2

public class Solution {
    public bool CanMakeSubsequence(string str1, string str2) {
        int i = 0, j = 0;
        int n1 = str1.Length, n2 = str2.Length;
        
        while (i < n1 && j < n2) {
            char original = str1[i];
            char incremented = (char)(((str1[i] - 'a' + 1) % 26) + 'a');
            
            if (original == str2[j] || incremented == str2[j]) {
                j++;
            }
            i++;
        }
        
        return j == n2;
    }
}

var canMakeSubsequence = function(str1, str2) {
    let i = 0, j = 0;
    
    while (i < str1.length && j < str2.length) {
        let char1 = str1[i];
        let nextChar1 = char1 === 'z' ? 'a' : String.fromCharCode(char1.charCodeAt(0) + 1);
        
        if (char1 === str2[j] || nextChar1 === str2[j]) {
            j++;
        }
        i++;
    }
    
    return j === str2.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n1)
空间复杂度O(1)

其中 n1 是 str1 的长度。算法只需要遍历一次 str1，每次操作都是常数时间，因此时间复杂度为 O(n1)。除了几个变量外不需要额外空间，空间复杂度为 O(1)。

相关题目