•
문제 설명 : 주어진 s문자열에서 p 문자열의 철자를 바꾼 문자(안바꾼 문자도 포함)가 시작되는 인덱스를 모두 구하여 반환
•
풀이 방법
◦
철자를 바꾼 문자를 일일히 모두 구해 대입하는 것은 매우 비효율적이다.
▪
이 될 수 있다.
◦
그래서 철자를 바꾼 문자를 구분하는 것이 핵심인데, 이때는 철자를 구성하는 요소의 갯수를 확인하면 된다.
▪
이를 위해, Counter / defaultdict를 사용하였다.
◦
이후 s는 sliding window 방식으로 p길이만큼 탐색하며, 철자의 갯수를 갱신하며 비교하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
p_info = Counter(p)
s_info = defaultdict(int)
result = []
left, right = 0, len(p) - 1
# p가 더 긴 경우
if len(p) > len(s):
return []
# 첫 p만큼 범위 확인
for i in range(len(p)):
s_info[s[i]] += 1
# 슬라이딩 윈도우로 탐색하며, s 탐색 범위내 요소와 p요소가 동일한지 확인
while right < len(s) - 1:
if s_info == p_info:
result.append(left)
s_info[s[left]] -= 1
s_info[s[right + 1]] += 1
if s_info[s[left]] == 0:
del s_info[s[left]]
left += 1
right += 1
# 마지막 범위 추가 확인
if s_info == p_info:
result.append(left)
return result
Python
복사