[LeetCode/Java] 242. Valid Anagram

0. 문제

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

1. 문제 설명

• 문자열 t와 s가 주어진다.
• 만약 t가 s의 아나그램이면 true를 반환하라.

2. 문제 풀이

2.1. 접근법 : 해시맵

• 맵의 key 값으로 s의 각 문자를 넣고 value에 문자 개수를 넣는다.
• t의 문자를 탐색하면서 문자가 맵에 key 값으로 존재하면 해당 key 값의 value를 하나 낮추고, 낮춘 다음 0이 되면 key를 지운다.
  • 만약 문자가 맵에 key 값으로 존재하지 않고, key 값의 value가 1 이상이 아니라면 false를 반환한다.

3. 코드

class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> map = new HashMap();
        
        for (char chr : s.toCharArray()) map.put(chr, map.getOrDefault(chr, 0) + 1);
        
        for (char chr : t.toCharArray()) {
            if (map.containsKey(chr) && map.get(chr) > 0) {
                map.put(chr, map.get(chr) - 1);
                if (map.get(chr) == 0) map.remove(chr);
            }
            else return false;
        }
        if (map.size() > 0) return false;
        return true;
    }
}

4. 결과

5. 개선점

5.1. 시간 복잡도 개선 (참고)

• s의 길이와 t의 길이가 다르면 아나그램이 아니기 때문에 false를 반환한다.
• 26의 길이를 가지는 alphabet이라는 정수형 배열을 생성한다.
• alphabet 배열은 각 알파벳의 등장 번호가 나오고, 등장 횟수를 저장한다.
• s의 문자(알파벳을)를 배열의 인덱스 번호에 맞춰 + 1을 해준다.
• t의 문자를 탐색하면서 해당 인덱스의 값을 - 1을 한다.
• alphabet 배열의 원소를 탐색하면서 0이 아닌 값(1 == 남은 문자가 있음, 0 미만 == 부족한 문자가 있음)이 존재하면 false를 반환한다.
• 풀이

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        int[] alphabet = new int[26];
        
        for(int i = 0; i < s.length(); i++) {
            alphabet[s.charAt(i) - 'a'] ++;
        }
        
        for(int i = 0; i < t.length(); i++) {
            alphabet[t.charAt(i) - 'a'] --;
        }
        
        for(int num : alphabet) {
            if(num != 0) {
                return false;
            }
        }
        
        return true;
    }
}

• 결과