Group Anagrams

yyeahh·2020년 11월 29일

leetcode medium

LeetCode

목록 보기

9/9

Group Anagrams

문제설명

문자열 배열 strs가 주어질 때, 어떤 순서로 반환해도 상관없으니 같은 아나그램들끼리의 그룹형태로 반환하라.
아나그램은 배치만 다른 문자열이다.
모든 문자열은 소문자로 이루어져 있다.
```
1 <= strs.length <= 104
 0 <= strs[i].length <= 100
```
Input :
List<String> strs
Output :
List<List<String>>

문제해결방법

각 문자열들을 비교하며 아나그램들을 찾아내는 방법을 O(n^2)으로 매우 비효율적이다.

해시맵을 이용한다면 위의 방법보다는 쉬울 것이라 생각

아나그램의 특징인 '같은 문자들의 재배치'를 이용
각 문자열들을 정렬하면 같은 문자열들이 생길 것이고 그것들을 묶어 반환
key : 정렬된 문자열(String), value : 기존 문자열들(List<String>)

일단 전체적으로 strs을 한 번 돌 것이다.

정렬된 문자를 저장할 새로운 List변수를 생성 및 초기화한 뒤 해시맵에 put
만약 존재하는 키라면 존재하는 List에 add

그리고 얻어진 요소들을 해시맵의 키값을 받아 다시 돌면서 answer에 추가

코드

[2020.11.29] 성공

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> answer = new ArrayList<List<String>>();
        
        HashMap<String, List<String>> hash = new HashMap<String, List<String>>();
        
        for(String i : strs) {
            char[] tmp = i.toCharArray();
            Arrays.sort(tmp);
            String key = String.valueOf(tmp);
            
            if(hash.containsKey(key)) hash.get(key).add(i);
            else {
                List<String> t = new ArrayList<String>();
                t.add(i);
                hash.put(key, t);
            }
        }
        answer.addAll(hash.values());
        return answer;
    }
}