Leetcode - 567. Permutation in String

문제

s2가 s1문자열의 permutation을 포함하고 있다면 true를 리턴하라.

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

해결 아이디어

• permutation 이라서 back tracking을 떠올릴 수 있지만 그렇게 풀면 대단히 느려진다.
• permutation 이라는것은 각 문자의 frequency가 항상 동일하다는 뜻. 이를 이용해 해시테이블로 접근하면된다.
• 추가로 sliding window를 적용하면 O(n)에 해결이 가능하다.

풀이

class Solution {
public:
    bool check_same(char *f1, char *f2) {
        for (int i = 0; i < 26; i++) {
            if (f1[i] != f2[i])
                return false;
        }
        return true;
    }
    bool checkInclusion(string s1, string s2) {
        int len_s1 = s1.length();
        int len_s2 = s2.length();
        if (len_s1 > len_s2)
            return false;
        char freq1[26] = {0};
        char freq2[26] = {0};
        
        for (int i = 0; i < len_s1; i++) {
            freq1[s1[i] - 'a']++;
            freq2[s2[i] - 'a']++;
        }
        if (check_same(freq1, freq2))
            return true;
        for (int i = 1; i + len_s1 - 1 < len_s2; i++) {
            freq2[s2[i-1] - 'a']--;
            freq2[s2[i + len_s1 - 1] - 'a']++;
            if (check_same(freq1, freq2))
                return true;
        }
        return false;
    }
};