[Leetcode Top Interview 150] 242. Valid Anagram

난이도 : easy

문제링크

• 두개의 문자열이 주어진다 : s, t
• t가 s의 anagram이라면 true를 리턴하라

 

• anagram은 또 다른 단어의 재구성을 통해 원본 단어를 똑같이 만들 수 있는 단어를 뜻한다
• 반드시 모든 문자를 한번씩 사용하여 구성해야 한다
  • ex) s = "anagram", t= = "nagaram" => true
  • ex) s = "ab", t= = "a" => false (s의 문자 b를 사용하지 않았음)

 

1. 접근법

• 단어별 갯수를 관리하는 자료구조인 해시테이블을 이용한다

 

3. 구현 코드

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();

        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c)+1);
            } else {
                map.put(c, 1);
            }            
        }

        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) {
                return false;
            } else {
                if (map.get(c) == 0) {
                    return false;
                }

                map.put(c, map.get(c)-1);
            }
        }

        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                return false;
            }
        }

        return true;
    }
}

• 모든 문자가 쓰여졌는지 체크하기
  • Map의 entrySet을 순회하면서, entry의 value가 0인지 체크한다

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함