문제 설명
https://leetcode.com/problems/find-all-anagrams-in-a-string/
자세한 문제는 위 링크 참고. 대상 문자열 s가 주어지면, p 문자열의 애니어그램에 해당하는 부분의 시작 인덱스를 리턴하는 문제다. 여기서 애니어 그램이란 p가 “abc”라고 되어 있을때 abc, acb, bac, bca, cab, cba 와 같이 p에 있는 문자열 또는 뒤섞인 순서를 나타낸다.
첫번째 풀이 (타임아웃 에러)
첫번째 시도. Brute Force로 풀었다. 문제는 p가 s 만큼 긴경우 발생한다. 이 경우 주어진 시간 내에 문제를 풀 수 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# window 사이즈는 p의 길이
window_size = len(p)
result = []
for i in range(0, len(s) - window_size + 1):
# p에 있는 애들 다 나오는지 체크
#print(s[i:i+window_size])
tmp_p = list(p)
#print(tmp_p)
try:
for one in s[i:i+window_size]:
#print(one)
tmp_p.remove(one)
except ValueError as e:
#print(e)
continue
if len(tmp_p) == 0:
#print(f"found {i}")
result.append(i)
return result
두번째 풀이
슬라이딩 윈도우를 통해서 풀었다. 윈도우에 해당하는 문자열을 Counter를 통해 key - 등장횟수로 분류하고, 윈도우를 하나씩 옮길때 마다 왼쪽에 있던 값을 -1 하고 새로 등장하는 값을 추가하는 방식으로 p와 같은지를 체크해 나갔다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import Counter
def is_anagram(anagram, substring):
for k, v in substring.items():
try:
if substring[k] != anagram[k]:
return False
except:
return False
return True
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# window 사이즈는 p의 길이
window_size = len(p)
result = []
tmp_p = dict(Counter(p))
window_dict = dict(Counter(s[0:window_size]))
# print(window_dict)
# print(tmp_p)
if is_anagram(tmp_p, window_dict):
result.append(0)
for i in range(1, len(s) - window_size+1):
# 왼쪽값 삭제
window_dict[s[i-1]] -= 1
if window_dict[s[i-1]] == 0:
del window_dict[s[i-1]]
# 오른쪽 값 추가
if s[i + window_size-1] not in window_dict:
window_dict[s[i + window_size-1]] = 1
else:
window_dict[s[i + window_size-1]] += 1
# 해당 인덱스가 문자 없으면 그냥 패스
if s[i] not in p:
continue
# print(window_dict)
# print(tmp_p)
if (len(window_dict.keys()) or len(tmp_p.keys())) and is_anagram(tmp_p, window_dict):
result.append(i)
return result
위 코드로는 Success가 떴다.