[LeetCode] 242. Valid Anagram - Java

Valid Anagram - LeetCode

 

문제

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 * 104
• 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?

 

두 개의 문자열 s와 t가 주어졌을 때, s의 문자들을 재배열하여 t를 생성할 수 있는지 여부를 판별하는 문제이다.

 

---

 

내 풀이

HashMap 사용

class Solution {
    public boolean isAnagram(String s, String t) {

        Map<Character, Integer> map = new HashMap<>();

        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for(int i=0; i<t.length(); i++){
            char c = t.charAt(i);

            if(map.containsKey(c)){
                if(map.get(c) == 1){
                    map.remove(c);
                }else{
                    map.put(c, map.get(c) -1);
                }
            }else{
                return false;
            }

        }

        if(map.size() > 0) return false;

        return true;
    }
}

 

1. 해시 맵 map은 문자를 키로, 해당 문자의 빈도를 값으로 가진다.
2. 문자열 s를 순회하며
   • 현재 문자 c의 빈도를 map에 업데이트한다.
   • 이미 map에 c가 있다면, 해당 문자의 빈도에 1을 더하고, 없다면 새로운 키로 추가하여 빈도를 1로 설정한다.
3. 문자열 t를 순회하며
   • 현재 문자 c가 map에 있는지 확인한다
   • 있는 경우, 문자의 빈도가 1이라면 맵에서 해당 문자를 제거하고, 아니라면 빈도를 1 감소시킨다.
   • 없는 경우, 애너그램이 불가능하므로 false를 반환한다.
4. map 에 문자가 남아있는 경우도 애너그램이 불가능한 경우이므로 false를 반환한다.
5. 모든 로직을 통과하면 true를 반환한다.

 

• 시간복잡도 : O(m + n) = O(n) - 문자열 순회
• 공간복잡도 : O(n) - 해시 맵의 크기에 비례

 

---

 

다른 사람의 풀이

class Solution {
    public boolean isAnagram(String s, String t) {

        Map<Character, Integer> map = new HashMap<>();

         for (char x : s.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        for (char x : t.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) - 1);
        }

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

        return true;

    }
}

비슷한 로직이지만 훨씬 깔끔하다.

두 문자열을 모두 순회하며 빈도 차이를 맵에 저장하고 그 차이가 모두 0인지 확인하는 로직이다.

후… 처음부터 이렇게 깔끔하게 짜는 사람이 되도록 하자.