LeetCode 438 - Find All Anagrams in a String (Medium)

 

💡 문제

LeetCode - 438번

 

🎯 풀이 과정

문자열 s 에서 p 의 아나그램을 만족하는 모든 부분 문자열의 위치를 찾는 문제입니다.

문자열의 길이를 고려해서 최적의 시간 복잡도로 문제를 해결해야하는데, sliding window 를 활용하면

O(n) 에 모든 위치에서 아나그램을 판단할 수 있습니다.

먼저 p 를 구성하는 문자 빈도수 해시맵을 생성합니다.

이후 두 개의 포인터 left 와 right , 아나그램 구성에 필요한 문자 개수의 합을 위한 count 를 정의합니다.

count 가 0이 되면 모든 문자들이 필요한 빈도수만큼 발견되었다는 것을 의미합니다.

window 의 크기는 곧 p 의 길이와 같기 때문에 left 와 right 간의 간격이 window size 에 도달하면

left 를 하나 오른쪽으로 옮겨주는 과정을 수행합니다.

이때 이 문자가 아나그램 구성에 필요했던 문자라면 count 를 하나 증가시켜줍니다.

👨‍💻 코드

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const needed = freq(p)
    const windowSize = p.length

    if (windowSize > s.length) {
        return []
    }

    let left = 0
    let right = 0
    let count = p.length
    const answer = []

    while (right < s.length) {
        if (needed[s[right]] > 0) {
            count -= 1
        }
        needed[s[right]] -= 1

        if (count === 0) {
            answer.push(left)
        }

        const isMaxWindowSize = (right - left + 1) === windowSize
        if (isMaxWindowSize) {
            if (needed[s[left]] >= 0) {
                count += 1
            }
            needed[s[left]] += 1
            left += 1
        }

        right += 1
    }

    return answer
};

function freq(str) {
    const result = {}

    for (let idx = 0; idx < str.length; idx += 1) {
        const char = str[idx]
        if (char in result) {
            result[char] += 1
        } else {
            result[char] = 1
        }
    }

    return result
}