•
문제 설명 : 제공된 s1 문자열의 순열로 만들 수 있는 문자열이 s2에 포함되었는지 확인한다.
•
풀이 방법
◦
s1의 순열 → 이를 직접 구하면, s1의 길이가 S일때 S! 만큼 걸리기 때문에 시간 복잡도에서 불리할 수 있다.
▪
결국에는 s1에서 사용되는 알파벳으로 구성된 문자열인지만 확인하면 된다.
◦
s2에서 s1의 길이만큼을 가지는 문자열을 일일히 구하고, 그것들을 순회하며 실제 문자열과 Equal인지 확인하는 방식도 좋지않다.
▪
즉, 문자열의 직접 비교 대신 s1의 사용된 알파벳 정보 == s2의 탐색 범위에서 사용된 알파벳 정보 방식으로 접근해야한다.
▪
이를 위해, Sliding Window 방식으로 s2에 접근하였다.
•
탐색 범위의 가장 앞/뒤 만을 수정하며, s1의 정보와 비교하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# s1을 구성하는 알파벳을 미리 구한다
s1_info = Counter(s1)
s1_len = len(s1)
# s1의 길이만큼 s2를 확인할 때, 문자의 구성을 확인한다.
s2_info = defaultdict(int)
for i, ch in enumerate(s2):
# s1의 길이만큼은 갯수 확인만 한다
if i < s1_len:
s2_info[ch] += 1
continue
# 현재 탐색 범위의 문자가 s1의 구성 알파벳과 동일한지 확인한다.
# -> 이 말은 s1의 순열로 구성된 문자열인지 확인하는 것이다.
if s1_info == s2_info:
return True
# 탐색 범위의 가장 앞 문자 정보를 삭제한다.
s2_info[s2[i - s1_len]] -= 1
# 0개일 경우, 키를 삭제한다
if s2_info[s2[i - s1_len]] == 0:
del s2_info[s2[i - s1_len]]
# 새로운 탐색범위의 갯수를 추가한다.
s2_info[ch] += 1
# 가장 마지막에 동일한 경우가 있을 수 있기 때문에, for문이 끝난 후 마지막으로 확인한다.
return s1_info == s2_info
Python
복사