[LC] 438. Find All Anagrams in a String

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

Approach

sliding window 문제이다.
anagram 이려면
1. 두 문자열을 각각 sorting 했을 때, 그 결과가 같아야 한다. (➡️ Idea 1)
2. 즉, 두 문자열에 포함된 문자의 종류와 그 개수가 동일해야 한다. (➡️ Idea 2)

Idea 1: Sliding Window + Sorting (Time 👎🏻)

anagram을 찾기 위해 sliding window를 이동해가며 sorting을 사용했다.

이때, sliding window 내의 원소 개수는 p의 문자 개수와 같아야 한다.

통과는 했으나 runtime이 7338ms 나왔다..;

어차피 sliding window는 한 칸씩 이동하므로 매번 window 내 원소를 다시 sorting 할 필요가 없기 때문에, Idea 2를 떠올렸다.

Idea 2: Sliding Window + Counter (Time 👍🏻)

sliding window 내 모든 원소를 sorting 하는 것이 아닌, sliding window 내 원소들에 대한 counter를 지속적으로 업데이트 해나가는 방식을 떠올렸다.

[!note] counter를 생성하는 방법에는 (1) normal dict로 구현하기, (2) collections.Counter 사용하기, (3) 문자의 범위가 명확하다면 list 사용하기 가 있다.

나는 세 가지 방법으로 모두 풀어보았다.

counter 생성하기
- p에 대한 counter target을 생성한다.
- s 중 첫 window에 대한 counter in_wnd를 생성한다. 이때, 오른쪽 원소가 하나 부족하게끔 한다. (Counter(s[:len(p) - 1]))
for i, _s in enumerate(s[len(p) - 1:]): 로, 첫 window의 마지막 원소부터 순회한다.

이때, i = 현재 window의 첫 원소의 인덱스, _s = 현재 window에 새롭게 추가할 원소 이다.
1. in_wnd에 새롭게 (맨 오른쪽) 원소를 추가한다.
2. in_wnd와 target을 비교하여, 같으면 현재의 i 값을 기록한다.
3. in_wnd에서 (맨 왼쪽) 원소를 제거한다.
기록된 값을 반환한다.

📌 `collections.Counter`의 Rich Comparison (Python 3.10+)

ref: https://docs.python.org/3/library/collections.html#collections.Counter

Counter인 in_wnd와 target은, 값이 0이 되는 entry를 del 해줄 필요 없이 단순하게 ==로 비교하면 된다.

# sliding window
for i, _s in enumerate(s[n - 1:]):
    """
    i = 현재 window의 첫 원소의 인덱스
    _s = 현재 window에 새롭게 추가할 원소
    """

    # 새롭게 window에 원소 추가
    in_wnd[_s] += 1

    # target과 in_wnd가 같으면 anagram이므로 res에 window의 첫 인덱스 추가
    if target == in_wnd:
        res.append(i)

    # window의 첫 인덱스 삭제
    in_wnd[s[i]] -= 1

    # Counter를 사용하니 안 해도 된다! (rich comparison) ****
    # if not in_wnd[s[i]]:
    #     del in_wnd[s[i]]

이는 Counter에서 제공하는 rich comparison 기능 덕분이다. Leetcode의 python version은 3.11이므로 이에 해당한다.

💡 `Counter` 대신 `list`

문제의 constraint에서 lowercase English letters로만 이루어져 있다고 했으므로, 앞서 언급했듯 길이 26짜리 list를 사용해도 된다.

이때, index는 in_wnd[ord(문자) - ord("a")] 와 같이 접근해야 함을 잊지 말자!

ord(c): 해당 문자의 유니코드 코드 포인트를 나타내는 정수를 반환한다.

Complexity

Time: O(n) (O(|s| + |p|))
Space: O(1) (O(26))

seungriyou / algorithm-study