[leetcode] 242. Valid Anagram - Python

🔍 Problem

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

---

📰 문제풀이

• 제한 시간: 15분
• 성공 여부: 실패
• 실패 원인: s와 t의 길이가 다를 때 처리할 방법을 생각하지 못했다.

---

📃 Solving Process

1. 각 문자열의 사전 데이터를 만든다.
2. 최종적으로 각 문자열로 만든 사전 데이터가 같으면 서로 같은 알파벳으로 만든 단어 또는 구절이기 때문에 True를 반환한다. 아니면 False를 반환한다.

---

💻 Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_dict = dict()
        d_dict = dict()
        for word in s:
            s_dict[word] = s_dict.get(word, 0) + 1
        for word in t:
            d_dict[word] = d_dict.get(word, 0) + 1
        return s_dict == d_dict

---

⏱ Time Complexity

• s와 t의 길이만큼 각각 for 문으로 사전 데이터를 만든다.
• s의 크기를 N, t의 크기를 K라고 했을 때, 시간복잡도는 O(N + K) -> O(N)이다.

---

💾 Space Complexity

• 시간 복잡도와 같지만 사실 알파벳이라는 조건으로 s와 t 모두 최대 알파벳 26개 만큼의 공간만 필요하다.
• 따라서 O(1)로 표현할 수 있다.