[2주차] 242. Valid Anagram

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

Valid Anagram - LeetCode

---

📝 문제

두 개의 문자열 s 와 t가 주어진다. t가 s의 애너그램이면 true, 아니면 false 를 리턴하라.

* 애너그램은 어떤 단어의 문자의 순서를 바꾼 것을 말한다.

 

🎈 풀이

383. RansomNote 와 거의 비슷한 문제이다. 다만 이 문제는 두 단어의 각 문자 갯수가 정확히 맞아떨어져야 한다.

남으면 애너그램이 될 수 없다.

 

시간복잡도: O(n)

공간복잡도: O(n)

public boolean isAnagram(String s, String t) {
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i=0; i<t.length(); i++) {
        char c = t.charAt(i);
        int prev = map.getOrDefault(c, 0);
        map.put(c, prev + 1);
    }

    for (int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c) && map.get(c) > 0) {
            map.put(c, map.get(c) - 1);
        } else {
            return false;
        }
    }

    return map.entrySet().stream()
            .filter(e -> e.getValue() > 0)
            .count() == 0L;
}

• 3행: t 문자열을 순회하며 각 단어가 나온 횟수를 map 에 저장한다.
• 9행: s 문자열을 순회하며 각 단어가 나올 때 마다 갯수를 감소시킨다.
• 18행: map을 순회하며 value 가 0 이상인 키가 하나라도 존재하면 false 이고, 하나도 없으면 true 이다.