[리트코드] 438. Find All Anagrams in a String - js (sliding window)

1. 문제

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Find All Anagrams in a String - LeetCode

2. 코드

이 문제는 약간의 해시 맵 + 슬라이딩 윈도우로 푸는 문제다. 슬라이딩 윈도우로 풀어야할 줄은 생각도 못했는데 정답 코드를 보니 이해가 되었다.

const findAnagrams = (s, p) => {
    const answer = [];
    const map = new Map();
    // p 안에 포함된 요소들 개수 저장
    for (let char of p) {
        map.set(char, (map.get(char) || 0) + 1);
    }
    
    let l = 0;
    let r = 0; 
    let count = p.length;
    
    // 슬라이딩 윈도우
    // p에 포함된 요소가 발견되면 오른쪽으로 한 칸씩 가다가 요소를 다 찾으면 l을 배열에 push
    // 만약 r - 1이 p 길이와 같으면 = 한 윈도우의 검사가 끝났으면(한 윈도우 크기 = p.length)
    // l을 한 칸 오른쪽으로 옮기는데, 만약 옮기기 전 l 인덱스에 해당하는 요소가 p의 요소라면
    // 이후 윈도우 검사에 영향 안주게 s[l]에 해당 하는 map 값 + 1 & count + 1 하여 원상 복구 해두기
    while (r < s.length) {
        if (map.get(s[r]) > 0) count--;
        map.set(s[r], map.get(s[r]) - 1);
        r++;

        if (count === 0) answer.push(l);
        
        if (r - l === p.length) {
            if (map.get(s[l]) >= 0) count++;
            map.set(s[l], map.get(s[l]) + 1);
            l++;
        }
    }

    return answer;
};