[Leet Code] Valid Anagram

문제출처

https://leetcode.com/problems/valid-anagram/description/

문제

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.  

Example 1:  
Input: s = "anagram", t = "nagaram"  
Output: true  

Example 2:  
Input: s = "rat", t = "car"  
Output: false  

Constraints:  
1 <= s.length, t.length <= 5 \* 104  
s and t consist of lowercase English letters.  

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Anagram은 하나의 단어를 철자 순서를 바꿔 다른 단어로 바꾸는 것이다.
한글로 친다면 고무 - 무고 이 두 단어가 anagram이다.

풀이

#1 Sorting - O(n log n)

첫번째 방식은 Sorting을 이용하는 것이다.
s와 t가 결국 같은 철자 & 개수로 이루어지면 True를 반환한다란 점을 활용한다.
코드는 간단하지만, time complexity가 O(nlogn)이란 단점이 있다.

1. s와 t를 sorting한다
2. s(sort) == t(sort) 의 값을 return한다.

def isAnagram(s: str, t: str) -> bool: 
    return sorted(s) == sorted(t)

#2 Hashmap - O(n)

이번엔 Hashmap을 이용해 time complexity를 nlogn을 n으로 줄여보자.

1. Hashmap을 만들어 놓고, s의 각 알파벳의 종류 / 개수를 업데이트한다.
2. t의 알파벳 종류 / 개수를 hashmap으로 부터 제거한다.
3. hashmap이 0이 아닐 경우 (다른 알파벳이 있거나 알파벳 개수가 달랐단 뜻이니) False를 반환한다.

def isAnagram(s: str, t: str) -> bool:
    count = {}
    for i in s:
        count[i] += 1
    for i int:
        count[i] -= 1

    for val in count.values():
        if val != 0:
            return False
    return True

#3 Hashmap, using Counter - O(n)

Python에 내장된 Counter이란 기능이 있다.
Hashable object counting하는데 특화된 딕셔너리이다.
한 줄로 끝나서 for문을 사용하는 것보다 간단하고, time complexity도 동일하다.
다만 #2 번 솔루션은 n이 길 경우, iterate 하는 도중에 맞지 않은 값이 나오면 빨리 False를 return할 수 있단 점이 장점이 될 수도 있다.

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

Follow up :

What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

위 솔루션 모두 unicode와 ASCII 상관없이 동일하게 동작한다.
따라서 코드를 수정할 필요는 없으다.

하지만 "é" 같이 accent가 붙은 알파벳을 "e"로 표현하고 싶다면 Normalize를 고려할 수 있다.

import unicodedata
from collections import Counter

def isAnagram(s: str, t: str) -> bool:
# Normalize the strings to NFC
    s = unicodedata.normalize('NFC', s)
    t = unicodedata.normalize('NFC', t)
    return Counter(s) == Counter(t)