Finding Anagrams(anagram 찾기)

 

"abc"와 "bca"는 Anagram이다. anagram이란 이처럼 size가 같고, 같은 알파벳으로 이루어진 문자열을 말한다. 그럼 이러한 anagram을 찾으려면 어떠한 알고리즘을 써야할까?

가령 s="abcdebacb", p="cab"일 때, s에서 p와 anagram인 문자열의 인덱스를 찾는다고 해보자.

 

그럼 어떠한 것이 같아야 anagram이라고 할 수 있을까?

1. size - p의 사이즈만큼 s를 slicing하면 되므로 간단!!

2. 사용하는 알파벳 종류

3. 등장하는 알파벳의 빈도수

 

이 땐, 2와 3을 비교하기 위해선 비트마스크를 사용하면 된다. 알파벳은 총 26개이므로 26개의 array를 만들고 각 알파벳의 등장 빈도수만큼 + 해준다. p="cab"이므로 p의 비트마스크 p_mask=[1,1,1,0,...,0]이 된다. 마찬가지로 s에서 처음 3글자 "abc"의 비트마스크 s_mask=[1,1,1,0,...,0]이 된다. 이 때 p_mask와 s_mask가 동일하므로 둘은 anagram인 것이다. 이 같은 방법을 len(p)만큼의 window가 s를 지나가면서 비교를 하면 된다.(sliding window)

여기서 효율을 증가시킬 수 있는 부분은 s의 각 substring마다 비트마스크를 전부 갱신할 필요가 없다는 것이다. 즉, 처음 "abc"와 p를 비교하고 난 뒤, window를 1칸 움직여 "bcd"와 p를 비교할 때는 기존 s_mask에서 a자리만 -1해주고 d자리만 +1해주면 된다. 다시금 "bcd" 전체를 검토해서 비트마스크를 갱신하지 않아도 되는 것이다.

 

관련 문제

---

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

Find All Anagrams in a String - LeetCode