[LeetCode] 567. Permutation in String

https://leetcode.com/problems/permutation-in-string/description/?envType=daily-question&envId=2024-10-05

leetcode - Permutation in String

문제 유형 : 슬라이딩 윈도우, 해시

문제 난이도 : Medium

 

문제

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

 

두 문자열 s1과 s2가 주어진다.

만약 s2가 s1의 순열을 포함한다면 true를, 아니면 false를 반환하시오.

즉, s1의 순열 중에서 s2의 부분문자열이 된다면 true를 반환하시오.

 

풀이

이 문제의 중점은, s2의 substring과 s1이 애너그램 관계인가이다.

즉, s2에 있는 길이가 s1의 길이인 substring들에 대해서 윈도우를 맞추고 밀어나가면서 조사하면 된다.

 

우선, s1의 길이가 s2의 길이보다 작으면 false이다.

각 문자의 빈도를 담는 26길이의 배열을 만든다.

s1을 읽으면서는 늘리기만 하고, s2를 읽으면서는 지정한 범위에 한해서 줄일 것이다.

우선, s1을 순회하면서 문자의 빈도를 설정한다.

 

세 개의 변수 left, right, to_match를 만든다. to_match는 앞으로 맞춰야 할 글자수이다.

right을 오른쪽으로 밀면서, count[right]이 0보다 크면, s1의 있는 글자와 매칭된다는 뜻으로, to_match를 1 낮춘다.

  그리고, count[right]을 그와 별개로 1 낮춘다. 

  그 뒤, right을 오른쪽으로 민다.

to_match가 0이면,  true를 반환한다.

left가 s1의 길이만큼 right와 벌어졌다면, left도 오른쪽으로 민다.

밀면서, count[left]를 다시 1 높인다. 이제 범위 밖이니 복구한다는 의미이다.

1 높였는데 count[left]가 양수라면, to_match를 1 높인다. 이제 그 칸은 다시 메꿔야 하기 때문이다.

 

위 과정을 right가 s2를 순회하는동안 true를 반환하지 못하면, false를 반환하면 된다.

 

코드

C++

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

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) return false;

        vector<int> count(26, 0);
        for (char c : s1) {
            count[c - 'a']++;
        }

        int left = 0, right = 0, to_match = s1.size();
        
        while (right < s2.size()) {
            if (count[s2[right] - 'a'] > 0) {
                to_match--;
            }
            count[s2[right] - 'a']--;
            right++;

            if (to_match == 0) return true;

            if (right - left == s1.size()) {
                if (++count[s2[left] - 'a'] > 0) {
                    to_match++;
                }
                left++;
            }
        }

        return false;
    }
};