LeetCode - 242. Valid Anagram

[LeetCode] 242. Valid Anagram

LeetCode 242번 문제를 풀어보았다.. Link

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Intuition

두 String이 Anagram인지 아닌지 판별하는 문제.

Anagram이라면 Character가 배열된 순서는 다르나 이루는 성분의 종류와 개수는 같고, 아니라면 성분의 종류와 개수가 다를 것이다.

Approach

1. Brute force 방식: s의 element 하나가 있으면 t의 element와 하나씩 비교하면서 같으면 해당 t의 element를 pop하고, 같은게 없으면 False를 return
2. Dictionary를 활용하여 같은 Key일 때 그 value가 같은지 확인하는 방법, Dictionary에는 s, t에 해당 element의 개수가 저장됨
3. Sorting하여 같은지 같지 않은지 확인하는 방법

Complexity

• Time complexity:

  s와 t의 개수를 각각 n과 m이라고 할 때, 1번 방식은 \(O(N^2)\), 2번 방식은 \(O(n+m)\), 3번 방식은 \(O(nlogn + mlogm)\)

• Space complexity: 1번 방식은 \(O(1)\), 2번 방식은 \(O(n+m) = O(n+m)\), 3번 방식은 \(O(1)\)

My Code

2번 방식을 사용하여 푸는 방법.. Key error를 방지하기 위한 get 함수를 쓰게되면 if문을 남발할 필요없이 코드가 좀 더 단순해진다.

class Solution:
    def rob(self, nums):
        if len(s) != len(t):
           return False
        cs, ct = {}, {}
        for i in range(len(s)):
            # key error를 피하기 위함, s[i] key가 없으면 0을 반환
            cs[s[i]] = 1 + cs.get(s[i], 0)
            ct[t[i]] = 1 + ct.get(t[i], 0)
        
        for c in cs:
            if cs[c] != ct.get([c], 0):
                return False
        
        return True

공간복잡도가 O(1)이어야 한다는 제한사항이 있다면 다른 방법을 생각해야한다.

Approach에 쓰여있는 1번 또는 3번 방식을 쓰면 가능하다.

3번 방식으로 풀어보면..

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if sorted(s) == sorted(t):
            return True
        else:
            return False
        
        # return sorted(s) == sorted(t)

python의 sorting 알고리즘은 O(nlogn)으로 알려져있고, 공간복잡도도 O(1)이라 적합할 수도 있지만 실제 Interview에서는 Interviewer한테 물어봐야한다고..