[LeetCode] 49. Group Anagrams

49. Group Anagrams

LeetCode

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

문자열 배열 strs가 주어질 때, 애너그램(anagrams)끼리 그룹으로 묶으십시오. 결과값은 어떤 순서로든 반환할 수 있습니다.

 

Example

Input
strs = ["eat","tea","tan","ate","nat","bat"]

Output
[["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation
There is no string in strs that can be rearranged to form "bat".The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Input
strs = [""]

Output
[[""]]

---

1. 문제 요구사항 분석

유입된 문자열들을 그룹화하는 문제: 여기서 그룹화란 같은 알파벳을 사용하는 것끼리 묶는 것. ate, eat, tea가 a, e, t 이 세 가지 알파벳이 사용되어 하나로 그룹핑됨.

 

2. 접근 전략

😄 HashMap 사용: 시간복잡도 O(nlogn)

우선 들어온 문자열 하나를 Arrays.sort를 이용해서 정렬 진행
정렬된 문자열을 key 값으로 하고, value에 원 값을 넣음

 

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str: strs) {
            char[] charArray = str.toCharArray();
            // 들어온 문자열 정렬
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            
            // 동일한 문자열끼리 그룹핑
            List insert;
            if (map.get(sortedStr) == null) {
                insert = new ArrayList();
            } else {
                insert = map.get(sortedStr);
            }
            insert.add(str);
            map.put(sortedStr, insert);
        }

        List<List<String>> list = new ArrayList<>();
        for (List<String> value : map.values()) {
            list.add(value);
        }

        return list;
    }
}

 

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

Group Anagrams - LeetCode