[LeetCode] 2825. Make String a Subsequence Using Cyclic Increments

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

leetcode - Make String a Subsequence Using Cyclic Increments

문제 유형: 투 포인터, 문자열 처리

문제 난이도: Medium

 

문제

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.

 

두 문자열 str1과 str2가 주어진다.

인덱스당 최대 한 번의 연산으로 str1[i]의 한 글자를 1 늘릴 수 있다.

str2가 str1의 subsequence가 될 수 있다면 true를, 아니면 false를 반환하시오.

 

풀이

str1을 순차적으로 읽으면서, 한 번 또는 0번의 연산으로 str[j]와 같아진다면, j도 한 칸 민다.

최종적으로 j를 다 밀었다면, true이다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int n = str1.size();
        int m = str2.size();

        if(m > n) return false;

        int j = 0;
        for(int i = 0; i < n; ++i) {
            if(j < m && (str1[i] == str2[j] || str1[i] - str2[j] == -1) || (str1[i] == 'z' && str2[j] == 'a'))
                ++j;
            if(j >= m) return true;
        }
        return j >= m;
    }
};