[LeetCode] 242. Valid Anagram

242. Valid Anagram

Easy

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?

---

문제 풀이

• 아나그램이란 단어의 알파벳을 재배치 했을때 같은 알파벳, 그리고 개수가 맞을때를 의미한다.
• 두개의 문자열이 주어지고 문자열들이 아나그램이면 True를 리턴, 아니면 False를 리턴한다.
• 결과적으로 알파벳의 순서는 상관없으며 각각 알파벳의 갯수들이 같은지를 알아보면 된다.
• 문제 제한을 보면 5 * 10^4 인데 브루트 포스로 풀면 아슬아슬 하게 통과할 것 같다.

Sorting

• 알파벳들의 개수를 확인하기 위해서는 직접 알파벳의 개수를 세거나 해야한다.
• 하지만 정렬을 이용하면 아나그램들은 같은 문자열이 되어버린다. 
• 알파벳 각각의 개수들이 같다면 정렬을 했을때 같은 모양이 나온다.
• 파이썬의 정렬은 기본적으로 O(NlogN)의 시간복잡도가 걸린다.
• 두가지 문자열을 정렬하고 리턴을 두개의 문자열 비교 결과로 정해준다.

Hash Table (Counter)

• 해쉬 테이블을 사용할때 알파벳들의 개수를 각각 세어 저장해주고 그 해쉬테이블을 비교하는 방식으로 풀 수 있다.
• 하지만 파이썬에는 Counter 라이브러리가 있는데 이는 자동으로 각 데이터의 개수를 자동으로 세어 딕셔너리에 저장해준다.
• Counter는 알파벳을 하나하나 확인하면서 알파벳을 키로 개수를 값으로 저장한다.
• 만약 for 문으로 푼다면 아스키코드 혹은 알파벳을 키로 저장하여 하나씩 1을 더해준다.
• 정렬 풀이방법 처럼 딕셔너리를 비교한 결과 값을 리턴 값으로 내보내면 된다. 

소스 코드

Sorting

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # sorting
        s1 = sorted(list(s))
        s2 = sorted(list(t))
        return s1 == s2

Hash Table (Counter)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # hash table
        hash_table1 = Counter(s)
        hash_table2 = Counter(t)
        return hash_table1 == hash_table2