[LeetCode] - 49.Group Anagrams

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

Group Anagrams - LeetCode

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

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

 

Example 2:

Input: strs = [""]
Output: [[""]]

 

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

풀이방법

입력값(str)의 길이가 10^4이니까, 시간복잡도는 O(n), O(nlogn)정도로 생각했다. 즉, for문 하나에, if문 정도.??

알고리즘이 익숙하지 않은 나에게, 이정도가 최선의 접근이다.

 

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

        for(String s : strs) {
            // 키를 정렬 후 String 형태로 다시 변환
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);

            // 만약 key가 없으면 map key 추가, 있으면 value에 add
            if(!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}