49. Group Anagrams

• 주어진 문자열 배열 strs 에 대해서 서로 anagram인 관계인 문자열끼리 묶어서 set을 만들고 그 set의 목록을 돌려주는 문제.

• 두 문자열이 anagram이라는 것은 각 알파벳의 출현 빈도가 동일하다는 뜻이다.

• 따라서 각 글자가 동일한 빈도로 출현한 문자열끼리 묶으면 되는 문제이다.

• 다만 동일한 출현 빈도임을 비교하기 위해서 unique한 key를 만들어야 하는데 이 때 더 효율적인 방법을 찾는 것이 필요하다.
• 단순히 integer를 문자열로 바꿔서 구분자로 join하는 방법도 있겠지만 아래 풀이에서는 byte array를 활용하여 key를 만들었다.
• 이는 각 문자열의 길이가 100이하인 점을 이용한 것이다 (최대 출현 빈도가 100이므로 byte 범위내에 들어오게 된다).

class Solution {
    String toHashKey(String s) {
        byte[] counter = new byte['z' - 'a' + 1];
        for (int i = 0; i < s.length(); ++i) {
            ++counter[s.charAt(i) - 'a'];
        }
        try {
            return new String(counter, "UTF-8");
        } catch (Exception e) {
            return "";
        }
        
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            String key = toHashKey(strs[i]);
            List<String> set = map.computeIfAbsent(
                key, (_) -> new ArrayList<String>());
            set.add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }
}