LeetCode 49. Group Anagrams 자바 문제 풀이

문제

Group Anagrams - LeetCode

문제 해결 방법

-아나그램으로 순서를 바꾼 단어들을 모으는 문제입니다.

-알파벳 순서를 바꿔도 모두 똑같은 문자열이 사용됬다는것을 확인하려면, 정렬을 해야 합니다.

-eat 이든 tea이든 정렬하면 똑같은 문자열이 나옵니다.

-해쉬맵을 이용하여 정렬된 문자열을 키로 사용하고, 똑같은 키가 나오는 문자열을 모으면 됩니다.

https://github.com/eunhanlee/LeetCode_49_GroupAnagrams_Solution.git

시간복잡도: O(nk), 공간복잡도: O(nk)

N은 문자열 배열의 길이

K는 배열 내 문자열의 최대 길이

class Solution {
    /**
     * 문자열 배열에서 아나그램을 그룹화합니다.
     *
     * @param strs 입력 문자열 배열
     * @return 그룹화된 아나그램을 담은 리스트의 리스트
     */
    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);

            // 정렬된 문자열이 해시맵에 존재하는지 확인합니다.
            if (!map.containsKey(sortedStr)) {
                // 존재하지 않을 경우, 그룹을 위한 새로운 리스트를 생성합니다.
								// 문제에서 빈 리스트를 원하기 떄문입니다.
                map.put(sortedStr, new ArrayList<>());
            }

            // 원래 문자열을 해당 그룹에 추가합니다.
            map.get(sortedStr).add(str);
        }

        // 해시맵의 값들을 리스트로 변환하여 반환합니다.
        return new ArrayList<>(map.values());
    }
}