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

难度: Medium

给你一个下标从 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⁵
1 <= str2.length <= 10⁵
str1 和 str2 只包含小写英文字母。

Submission

运行时间: 82 ms

内存: 16.3 MB

MAP = dict(zip(ascii_lowercase, ascii_lowercase[1:] + 'a'))

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i = 0
        n = len(str2)
        for c in str1:
            if c == str2[i] or str2[i] == MAP[c]:
                i += 1
                if i == n:
                    return True
        return False

Explain

该题解依据的思路是通过单次循环遍历str1，同时尝试匹配str2中的字符。对于str1中的每个字符，我们检查它是否与str2中当前位置的字符相同，或者通过单次循环递增能变成str2中的该字符。如果条件满足，str2的索引向前移动一位。如果str2的所有字符都能按顺序在str1中找到匹配（包括循环递增的匹配），则返回true，否则遍历结束后返回false。

时间复杂度: O(n)

空间复杂度: O(1)

from string import ascii_lowercase

MAP = dict(zip(ascii_lowercase, ascii_lowercase[1:] + 'a'))  # 创建字符的循环递增映射

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i = 0  # str2的索引初始化
        n = len(str2)  # str2的长度
        for c in str1:  # 遍历str1中的每个字符
            if c == str2[i] or str2[i] == MAP[c]:  # 检查字符匹配或循环递增匹配
                i += 1  # 匹配成功，移动str2的索引
                if i == n:  # 如果str2的所有字符都已匹配
                    return True  # 返回true
        return False  # 遍历结束，未能完全匹配，返回false

Explore

使用循环递增的映射（MAP）可以直接通过查表的方式快速得到字符的下一个值，这种方法相较于每次计算字符的下一个值具有更高的效率和更简洁的代码实现。查表减少了运算量，特别是在需要频繁进行字符转换的情况下更显优势。

算法的目标是检查是否可以在str1中通过顺序遍历找到一个子序列，该子序列可以通过字符的直接匹配或循环递增匹配str2。跳过str1中的更多字符可能会错过潜在的匹配机会，因为每个字符都可能是str2中下一个所需的匹配字符，无论是直接还是循环递增匹配。因此，逐个检查str1的每个字符是必要的。

算法在遇到str1中的字符时，首先检查是否与str2中当前索引的字符直接相等；如果不相等，则检查通过循环递增是否能匹配到str2的当前字符。这一决策是基于当前str1字符的两种可能匹配方式，优先考虑直接匹配，若不成功再考虑循环递增匹配。

此算法设计为检查str2是否可以是str1的子序列，其中str1的字符可以通过直接匹配或循环递增匹配str2的字符。若str2的顺序在str1中无法找到严格的顺序匹配，则算法将返回false。例如，对于str1为'abcd'且str2为'bac'的情况，算法不能处理，因为虽然'b'和'a'在'abcd'中，但它们的顺序与str2中的顺序不符，因此算法会返回false。