[LeetCode] 242. Valid Anagram

Problem

https://leetcode.com/problems/valid-anagram/description/?envType=study-plan-v2&envId=top-interview-150

 

Solution

Hash

문자열이 각각 동일한 수의 char 을 가지고있는지 체크하는 간단한 문제.

hash 를 사용하여 각각의 character 의 수를 count 한다.

python에 Counter 모듈을 사용해서 한 줄로 해결한 코드를 발견하였다.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

 

Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        answer = True
        mapS, mapT = {}, {}

        if len(s) != len(t):
            return False

        for char in s:
            if char in mapS:
                mapS[char] += 1
            else:
                mapS[char] = 1
        
        for char in t:
            if char in mapT:
                mapT[char] += 1
            else:
                mapT[char] = 1
        
    
        for i in range(len(s)):
            if s[i] not in mapT:
                return False
            if mapS[s[i]] != mapT[s[i]]:
                return False
    
        return answer

 

Complexity

Time Complexity

for문을 문자열의 길이만큼 순회하며 체크하였다.

마지막 각 dictionary의 문자열 확인도 for 문을 돌며 체크하였으므로 시간복잡도는 최종적으로 O(N) 이다.

 

Space Complexity

 문자열의 길이만큼 dictionary 를 사용하였으므로 O(N) 이다.