그룹 애너그램

리트코드 문제: Group Anagrams

목적:

문자열 strs의 배열이 주어지면 애너그램을 함께 그룹화합니다. 어떤 순서로든 답변을 반환할 수 있습니다.

애너그램은 일반적으로 모든 원래 문자를 정확히 한 번만 사용하여 다른 단어나 구의 문자를 재배열하여 형성된 단어 또는 구입니다.


패턴: 배열 및 해싱


접근하다:

결과에 대한 2D 목록을 만듭니다.

HashMap 만들기: 키 = 정렬된 단어, 값 = 애너그램 목록.

입력 문자열 배열을 반복하고 입력을 정렬합니다.

정렬된 입력이 해시맵에 있지 않거나 정렬된 입력이 정렬되지 않은 입력과 동일한 경우 정렬된 입력을 키로 추가하고 정렬되지 않은 입력을 아나그램으로 추가합니다.

정렬된 입력이 해시맵의 키로 이미 존재하는 경우 정렬된 키를 가져와 정렬되지 않은 입력을 아나그램 목록에 추가합니다.

해시맵을 반복하고 각 애너그램 목록을 결과 목록에 추가합니다. 결과를 반환합니다.

빅오 표기법:

시간 복잡도: O(m * nlog(n))
각 문자열에 대해 n번 반복합니다.
O(n log(n))인 Arrays.sort()를 사용하여 각 문자열을 정렬합니다.

공간 복잡도: O(n * m)
스토리지를 위해 추가 데이터 구조를 사용합니다.
결과를 저장할 2D 목록이 있습니다.
요소를 저장하기 위한 해시맵이 있습니다.

암호:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // input: string array 
        // output: 2D list 
        List<List<String>> result = new ArrayList<List<String>>();

        Map <String, List<String>> hashMap = new HashMap<>();

        for(String str : strs){
            char [] array = str.toCharArray();
            Arrays.sort(array);

            String sortStr = str.valueOf(array);

            // edge case if current == key then add to key. 
            if(sortStr == str || !hashMap.containsKey(sortStr)){
                List <String> anagram = new ArrayList<>();
                anagram.add(str);
                hashMap.put(sortStr, anagram);
            } else {
                hashMap.get(sortStr).add(str);
            }
        }

        // add anagram list into result 
        for(String s : hashMap.keySet()){
            result.add(hashMap.get(s));
        }

        return result;
    }
}