[leetcode] 49 group anagram

 

49. Group Anagrams

 

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"]]

 

 

해답

 

요즘 머리가 굳어서 그런가... 어떤 문제건 일단 brute force로 무식하게 들이박고 시작하는 버릇이 생겨서 고생중이다 ...

애너그램을 정렬하면 똑같아짐 (tea, eat, ate를 정렬하면 모두 aet임) -> String을 Char[]로 뜯어서 정렬 후 비교하기

똑같아진 값, 원래 애너그램값을 모아야함 -> 똑같아진 값이 key, 원래 애너그램 값이 value인 HashMap을 사용했다. 

 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    	// 애너그램 정렬된 버전을 key, strs에 들어간 원래 애너그램 값들을 모은 리스트를 value로 사용
        HashMap<String, List<String>> map = new HashMap<>();
        
        
        for (String str: strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            // 애너그램이 정렬이 되는 순간 모두 똑같아지기 때문에 key값으로 사용
            String key = String.valueOf(chars);
            
            if (map.containsKey(key)) {
                map.get(key).add(str);
            }
            else {
                map.put(key, new ArrayList<>());
                map.get(key).add(str);
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        for (String key: map.keySet()) {
            result.add(map.get(key));
        }
        
        return result;
    }
}