49. Group Anagrams

문제

https://leetcode.com/problems/group-anagrams/

코드

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        for(String str : strs){
            char[] tmp = str.toCharArray();
            Arrays.sort(tmp);
            String k = new String(tmp);
            if(m.get(k) == null)
                m.put(k, new ArrayList<>());
            m.get(k).add(str);
        }

        for(String key : m.keySet())
            res.add(m.get(key));

        return res;

    }
}

피드백

• 일단 내 풀이는 시간 복잡도가 O(MNlogN)이다.
• 여기 O(MN) 짜리 풀이가 있다.
  • https://leetcode.com/problems/group-anagrams/discuss/19233/O(M-*-N)-algorithm-using-hash-without-sort()
  • 각 영문자를 소수로 치환해서 곱해서 hash 값을 만든다.
  • 소수이기 때문에 하나의 단어가 가지는 hash 값이 unique하다고 할 수 있다.