31 lines
1.3 KiB
Python
31 lines
1.3 KiB
Python
# Valid Anagram
|
|
|
|
from collections import Counter
|
|
|
|
class Solution:
|
|
def isAnagram(self, s: str, t: str) -> bool:
|
|
c = Counter(s)
|
|
for k in t:
|
|
if c.get(k, 0) == 0:
|
|
return False
|
|
c[k] -= 1
|
|
if c[k] == 0:
|
|
del c[k]
|
|
if len(c) == 0:
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
|
|
"""
|
|
걸린 시간: 8분
|
|
|
|
복잡도: s의 빈도수 세는 것이 O(n), t를 순회하면서 확인하는 것 O(n), 마지막에 c의 길이 확인하는 것은 소문자 26개이므로 O(1)이므로 전체 시간복잡도는 O(n)이다.
|
|
Counter로 s의 빈도수를 센 것말고는 없는데 이것도 소문자 26개가 최대 길이이므로 공간복잡도는 O(1)이다.
|
|
|
|
해설: anagram은 문자열 구성을 그대로 써서 재배열했을 때 만들 수 있나 여부이다.
|
|
따라서 s의 글자 빈도 수를 세고, t가 그 글자와 다른 글자를 썼거나, 빈도수가 다르다면 False 아니라면 True로 출력한다.
|
|
이때 s가 t를 포함한다면 False로 반복문을 나올 수 없으므로 Counter 객체에서 빈도수가 0이 된것은 key를 삭제하여 빈도수가 완전히 같은지 확인한다.
|
|
|
|
근데 사실 이럴 필요 없이 길이가 다르면 바로 False처리하고, Counter(s) == Counter(t) 여부만 확인해도 끝난다..
|
|
""" |