LeetCode 49. Group Anagrams (Java)

문제 링크

The problem link : LeetCode 49. Group Anagrams

문제 요약

1. 문자열 배열 strs가 주어진다.
2. 애너그램으로 재배열했을때 같은 단어들끼리 그룹으로 뭉쳐라.
3. 그룹으로 뭉쳐진 단어들을 반환하라. 이때 순서는 상과없다.

문제 풀이

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();

        for(int i=0; i<strs.length; i++){
            String temp = strs[i];
            char[] arr = temp.toCharArray();
            Arrays.sort(arr);
            String orderedTemp = new String(arr);

            if(map.containsKey(orderedTemp)){
                map.get(orderedTemp).add(temp);
            } else {
                map.put(orderedTemp, new ArrayList<>());
                map.get(orderedTemp).add(temp);
            }
        }

        return new ArrayList<>(map.values());
    }
}

문자열을 하나하나 오름차순으로 정렬해서 map에 저장되어있는지를 판별하는게 핵심 로직

시간복잡도

시간복잡도 : O(n*m*log(m))

• n : strs의 길이
• m : strs에 포함된 문자열 중 최대로 긴 문자열의 길이

공간복잡도 : O(n*m)