242. Valid Anagram

haaaalin·2023년 8월 31일

알고리즘 코테

LeetCode

목록 보기

19/31

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

문제

t가 s의 애너그램인지 확인하자.

t와 s는 영문 소문자로 구성

입력

문자열 s, t

출력

true/false

Anagram이란?
다른 단어나 구의 글자를 재배열하여 만든 단어 또는 구문 (글자를 모두 한 번만 사용)

나의 풀이

접근

전에 풀었던 문제인, 383. Ransom Note 의 문제와 거의 유사한 문제였다.

Ransom Note 문제는, 문자열 s와 t가 있으면, t에 있는 문자들로 s를 만들 수만 있다면 true를 반환하는 문제였다.

하지만 이번 문제는, t에 있는 문자와 s에 있는 문자 수가 정확히 일치해야 한다는 점이 달랐다.

따라서, 앞서 풀었던 문제의 풀이에 몇 줄만 추가하면 해결됐다.

구현 코드

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] charCounts = new int[26];
        
        for (char c : t.toCharArray()) {
            charCounts[c - 'a']++;
        }

        for (char c : s.toCharArray()) {
            charCounts[c - 'a']--;
            if (charCounts[c-'a'] < 0)
                return false;
        }
        int answer = Arrays.stream(charCounts).sum();

        return answer == 0;
    }
}

알파벳 숫자만큼의 int 배열을 선언한다.
그리고 t의 글자를 for문을 실행하면서 탐색한다
- charCounts에 count값을 저장한다.
s의 글자를 for문을 실행하며 탐색
- s의 문자와 같은 t 문자의 count값을 1 감소
- 만약 t가 가지고 있는 문자보다 s의 문자가 더 많다면, 바로 false를 반환
for문 실행 후, charCounts 배열의 총합이 0인지를 반환 (합이 0이 아니라면, t의 글자 수가 더 많았다는 의미)

결과

Time: O(n)
Space: O(1)

다른 풀이

나의 풀이와 비슷하지만, HashMap 을 사용한 코드가 있었다.

아래의 풀이에선 따로 합을 구하지 않았다.

s는 count 값을 더하고, t는 count 값을 감소
따로 또 for문을 실행해 해당 글자의 count 값이 0이 아니라면 false를 바로 반환하는 방법

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> count = new HashMap<>();
        
        for (char x : s.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        
        for (char x : t.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) - 1);
        }

        for (int val : count.values()) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
}