[ Top Interview 150 ] 242. Valid Anagram

문제

242. Valid Anagram

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.

• Input : 두 문자열 s, t
• Output : s 문자열을 재배치하여 t를 만들 수 있는가?
  • 특정 문자를 중복하여 사용하거나 특정 사용하지 않을 수 없음

알고리즘 전략

• 전략 1. Map 자료구조 사용

  • ['문자' - '나온 횟수'] 로 구성된 Map을 이용
  • s를 이용하여 Map을 만들고, t를 이용하여 Map의 횟수를 하나씩 차감해나감
  • Time complexity : O(n)
  • Space complexity: O(n)

• 전략 2. Sorting

  • 두 문자열이 동일한 문자와 동일한 개수로 쓰여있다면, Sorting했을 때 동일한 배열이 된다.
  • Time complexity : O(nlogn)
  • Space complexity: O(n)

답안 1

• Map 자료구조 이용
  • Time complexity : O(n)
  • Space complexity: O(n)

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> countOfLetter = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);
            int count = countOfLetter.getOrDefault(letter, 0);
            countOfLetter.put(letter, count + 1);
        }
        
        for (int i = 0 ; i < t.length(); i++) {
            char letter = t.charAt(i);
            int count = countOfLetter.getOrDefault(letter, 0);
            if (count <= 0) {
                return false;
            }
            countOfLetter.computeIfPresent(letter, (key, value) -> value - 1);
            countOfLetter.remove(letter, 0);
        }
        
        return countOfLetter.isEmpty();
    }
}

답안 1 리팩토링

• for문 안에 내용을 줄여 가독성을 높임

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;
    }
}

답안 2

• Sorting 이용 (Java 제공 라이브러리 사용)
  • Time complexity : O(nlogn)
  • Space complexity: O(n)

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        
        return Arrays.equals(sChars, tChars);
    }
}

답안 비교

• 기본적으로 Time complexity는 Map을 사용하는 방법이 더 좋음
  • 그럼에도 Sorting이 시간 성능이 더 잘 나오는 것은 제공되는 데이터의 길이가 그렇게 길지 않은 것으로 추정됨
    • 1 <= s.length, t.length <= 50,000
  • Map을 만들고 쓰는 데에 생각보다 비용이 많이 필요로 하는 것을 알 수 있었다.