[LeetCode] 567. Permutation in String

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

Permutation in String - Medium

 

s2 속에 s1의 permutation이 포함되어 있는지 구하는 문제다

여기서 permutation은 s1의 알파벳을 아무렇게나 배열한것을 의미한다.

 

permutation을 파악하면 되므로 s1에 포함된 알파벳들의 수를 저장해주고,

s2를 s1 size의 window로 훑으며 그 안에 포함된 알파벳들의 수와 비교해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size()>s2.size()) return false;
        int a[26] = {}, b[26] = {};
        for (char c:s1) a[c-'a']++;
        for (int i=0,j=0; i<s2.size(); i++) {
            b[s2[i]-'a']++;
            if (i>=s1.size()) b[s2[i-s1.size()]-'a']--;
            for (j=0; j<26; j++) if (a[j]!=b[j]) break;
            if (j==26) return true;
        }
        return false;
    }
};