[리트코드] 242. Valid Anagram

문제

https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150

Example 1:

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

Example 2:

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

 

Contraints:

 

• 1 <= s.length, t.length <= 5 * 10**4
• 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?

 

---

✔ 문제접근 #1 투포인터[통과] ⭕

Intuition
문자열 하나의 각 요소 등장횟수를 dict자료구조에 기록한다.

나머지 문자열과 비교하며 애너그램이 될 수 있는지 판단한다.

Algorithm
문자열s의 등장횟수를 dict 자료구조 h에 기록한다.

문자열 t를 순회하며 요소가 있다면 -- 카운트해주고, 만약 그러한 문자가 아예 없거나 개수가 0이라면 실패로 간주한다.

마지막으로 두 문자열의 길이가 다를 수 있기 때문에 기존에 등장횟수를 기록했던 s를 순회하며 h의 모든 값이 0인지 확인한다.

    def isAnagram(self, s: str, t: str) -> bool:
        
        h = defaultdict(int)
        for elem in s:
            h[elem] += 1
            
        for elem in t:
            if elem not in h:
                return False
            
            if h[elem] == 0:
                return False
            
            h[elem] -= 1
            
        # 만약 전체를 순회하며 남아있는 수가 있다면 실패
        for elem in s:
            if h[elem] != 0:
                return False
        
            
        return True

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 문자열 s 순차탐색 O(N)
  • 문자열 t 순차탐색 O(M)
  • 문자열 s 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N + M + N) = O(N + M)

• 공간복잡도 : O(N)
  
  • 추가적인 dict자료구조 사용

---

기타풀이 및 회고

두 문자열의 길이가 서로 다를 수 있기 때문에 정확히 일치하는 지 확인하기 위하여 h를 확인해주는 작업이 꼭 필요하다.

 

또 다른 풀이로는 두 문자열을 정렬하여 비교하는 방법이 있었다. 정렬하게 되면 두 문자열의 각 요소의 위치가 순서대로 매칭되어 비교하기 편리해진다. 하지만 정렬하는 시간복잡도 O(NlogN)을 주의해야한다.

 

문자열에 알파벳 소문자외에 다른 문자가 있을 때에는 a ~ z인 문자에 대해서만 수행하는 조건문이 필요할 것이다. python에서는 ord()함수를 사용하면 O(1)에 알파벳 소문자 범위 내에있는지 판단이 가능하다.