2825. Make String a Subsequence Using Cyclic Increments

Problem

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 make str2 a subsequence of str1 by performing the operation at 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.

https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments/

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⁵
• 1 <= str2.length <= 10⁵
• str1 and str2 consist of only lowercase English letters.

Test Cases

1
2

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('str1, str2, expected', [
    ("abc", "ad", True),
    ("zc", "ad", True),
    ("ab", "d", False),
])
class Test:
    def test_solution(self, str1, str2, expected):
        sol = Solution()
        assert sol.canMakeSubsequence(str1, str2) == expected

Thoughts

Python 里负数对正数取余数，结果也是正数，比如 -25 % 26 = 1。利用这个特性可以简化 cyclically increment 的边界处理。

Code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        n2 = len(str2)
        j = 0
        for c1 in str1:
            if (ord(str2[j]) - ord(c1)) % 26 <= 1:
                j += 1
                if j == n2:
                    return True

        return False

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章