Leetcode - 438. Find All Anagrams in a String

문제

s로 주어지는 문자열 안에서 p로 주어지는 문자열의 Anagram을 찾고 시작부분의 인덱스를 리턴하라.

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

해결 O(n) / O(1)

해시테이블과 sliding window기법을 사용하는 좋은 문제였다.
p크기 만큼의 윈도우를 s내에서 하나씩 오른쪽으로 이동하면서 체크하면 됨.

Runtime: 12 ms, faster than 92.59% of C++

class Solution {
    bool is_table_same(int *st, int *pt) {
        for (int i = 0; i < 26; i++) {
            if (st[i] != pt[i])
                return false;
        }
        return true;
    }
        
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int ssize = s.size();
        int psize = p.size();
        if (ssize < psize)
            return ret;
        int stable[26] = {0};
        int ptable[26] = {0};
        
        for (int i = 0; i < psize; i++) {
            ptable[p[i] - 'a']++;
            stable[s[i] - 'a']++;
        }
        if (is_table_same(stable, ptable))
            ret.push_back(0);
        
        for (int i = 1; i <= ssize - psize; i++) {
            stable[s[i - 1] - 'a']--;
            stable[s[i + psize - 1] - 'a']++;
            if (is_table_same(stable, ptable))
                ret.push_back(i);
        }
        return ret;
    }
};