[LeetCode/Top Interview 150] [Hash Table] 242. Valid Anagram

문제 링크: https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

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

Constraints:

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?

전략:

주어진 두 문자열로 아나그램을 만들 수 있는지 확인하는 문제이다.
Ransom Note문제와의 차이는 각 문자열의 모든 문자를 사용해야 한다는 점이다.
제약조건은 영문 소문자만으로 동일하므로 남는 문자가 있는지만 체크하면 해결될 것 같다.

코드 구현:

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] alpha = new int[26];
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        
        // s의 알파벳 집계
        for (int i=0;i<sa.length;i++) {
            alpha[sa[i] - 'a']++;
        }

        // t 만드는데 사용한 경우 제거
        for (int i=0;i<ta.length;i++) {
            if (--alpha[ta[i] - 'a'] < 0) return false;
            // 사용한 후 음수값이 되면 즉시 false 리턴
        }
        // 사용하고 남은 알파벳이 있어도 false
        for (int i=0;i<26;i++) {
            if (alpha[i]!=0) return false;
        }
        return true;
        
    }
}
Time: 2 ms (99.23%), Space: 43.11 MB (68.79%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0242-valid-anagram/0242-valid-anagram.java

개선 방안:

시간복잡도는 괜찮지만 공간복잡도가 조금 아쉽다. for 대신 forEach, toCharArray 대신에 charAt(i)를 사용해보자

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] alpha = new int[26];
        
        // s의 알파벳 집계
        for (int i=0;i<s.length();i++) {
            alpha[s.charAt(i) - 'a']++;
        }

        // t 만드는데 사용한 경우 제거
        for (int i=0;i<t.length();i++) {
            if (--alpha[t.charAt(i) - 'a'] < 0) return false;
            // 사용한 후 음수값이 되면 즉시 false 리턴
        }
        // 사용하고 남은 알파벳이 있어도 false
        for (int i : alpha) if (i != 0) return false;
        // 아나그램 아님
        return true;        
    }
}
Time: 3 ms (91.64%), Space: 41.58MB (98.71%) - LeetHub

Solutions 탭의 타인 코드:

public class Solution {
    public boolean isAnagram(String s, String t) {
        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 i : alphabet) if (i != 0) return false;
        return true;
    }
}
Time: 3 ms (91.64%), Space: 41.58MB (98.71%) - LeetHub

회고:

욕심이 생길수록 미묘한 차이에 집착하게 되지만, 시간복잡도와 공간복잡도의 트레이드 오프 관계를 생각해 보면 역시 포기할 때는 포기해야 겠다.
ps. forEach문의 속도가 더 빠른게 이렇게 체감이 되다니...