[Leetcode] 242. Valid Anagram_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '242. Valid Anagram'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Valid Anagram' 알고리즘 문제

 

STEP 2. 'Valid Anagram' 코드(code)

 

STEP 3. 'Valid Anagram' 해설

 

STEP 4. 'Valid Anagram' solution

 

반응형

 

STEP 1. 'Valid Anagram' 알고리즘 문제

 

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.

 

두 개의 문자열 s와 t가 주어지면 t가 s의 철자법이면 true를 반환하고 그렇지 않으면 false를 반환합니다. 애너그램은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어나 구문의 문자를 재배열하여 형성된 단어나 구문입니다.

 

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

---

STEP 2. 'Valid Anagram' 코드(code)

 

1. List 접근 방식

 

■ Runtime: 43 ms Beats 84.06% of users with Python3
■ Memory: 17.71 MB Beats 14.85% of users with Python3

 

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        '''
        To be anagram, s and t intended to be a same length 
        1. If, s and t length are not same, then False
        2. s.sort() and t.sort() are not same character in each data respectively. 
        '''

        # Case 1.
        if len(s) != len(t): return False

        # Case 2.
        s = sorted(list(s))
        t = sorted(list(t))

        for index in range(len(s)):
            if s[index] != t[index]:
                return False
        return True

---

2. Hash table 접근 방식 (Counter 미사용)

 

■ Runtime: 54 ms Beats 31.80% of users with Python3
■ Memory: 16.78 MB Beats 99.26% of users with Python3

 

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Case 1.
        if len(s) != len(t): return False

        # Case 2.
        s_count, t_count = {}, {}

        for char in s:
            if char in s_count:
                s_count[char] += 1
            else:
                s_count[char] = 1


        for char in t:
            if char in t_count:
                t_count[char] += 1
            else:
                t_count[char] = 1

        return s_count == t_count

---

3. Hash table 접근 방식 (Counter 사용)

 

■ Runtime: 33 ms Beats 98.83% of users with Python3
■ Memory: 16.83 MB Beats 91.01% of users with Python3

 

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Case 1: If the lengths are not equal, they cannot be anagrams.
        if len(s) != len(t): return False

        # Case 2: Use Counter to count the frequencies of characters in both strings.
        s_count = Counter(s)
        t_count = Counter(t)

        return s_count == t_count

---

STEP 3. 'Valid Anagram' 해설

 

첫 번째 방식은 string을 list 하여 순서를 정렬하여 검토했습니다. 다만, 이 경우 list에 정보를 담고, 또 이를 다시 한번 순서를 정렬하다 보니, memory 부분에서 큰 손해를 봤습니다.

 

두 번째 그리고 세 번째 방식은 dictionary을 활용하여 s와 t에 대해서 {알파벳:횟수}를 각각 계산하고 비교했습니다. 두 방식의 차이점은 collections 라이브러리 내 Counter 함수의 사용 여부입니다.

 

 

STEP 4. 'Valid Anagram' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 49 ms Beats 57.85% of users with Python3
■ Memory: 16.86 MB Beats 91.01% of users with Python3

 

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:  
        if len(s) != len(t):
            return False

        counter = {}

        for char in s:
            counter[char] = counter.get(char, 0) + 1

        for char in t:
            if char not in counter or counter[char] == 0:
                return False
            counter[char] -= 1

        return True

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '242. Valid Anagram'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.