[LeetCode] 49. Group Anagrams (JS)

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

Group Anagrams - LeetCode

핵심 아이디어

• 순서가 다른 문자열은 정렬하면 같은 문자열이 된다

 

복잡도

• 시간 복잡도: O(N * KlogK)
  
  • 문자열 N개 * K길이 문자열 정렬 KlogK
• 공간 복잡도: O(N)
  
  • anagrams hash map (이차원처럼 보이지만, 전체 개수는 N개이다)

 

설명

"문자열 배열을 받아 애너그램 단위로 그룹핑하라"

 

순서가 다른 문자열 애너그램은 정렬하면 같은 문자열이 된다는 것을 활용하여 이를 key로 사용한 hashMap에 문자열들을 리스트로 저장한다.

[...str]을 쓰면 str.split() 없이도 문자열이 배열로 바뀐다는 것을 배웠다.

 

코드 (Javascript)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const anagrams = strs.reduce((prevMap, str) => {
        const key = [...str].sort().join("");
        
        if(!prevMap.has(key)) {
            prevMap.set(key, [str]);
            return prevMap;
        }
        
        prevMap.set(key, [...prevMap.get(key), str]);
        return prevMap;
    }, new Map());
    
    return [...anagrams.values()];
};