LeetCode Group Anagrams (JavaScript)

링크 : https://leetcode.com/problems/group-anagrams/description/

문제 설명

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

Example 1:

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

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

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

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

---

문제 풀이

각 문자열이 정렬된 상태가 같다면 위치를 변경시켜 서로를 만들 수 있음 (ex) eat -> ate)

정렬된 문자열을 key로 dict 형태로 관리 -> key가 같다면 target 문자열을 추가

 

최종 리턴은 Object.values() 메서드를 이용 -> dict을 배열형태로 변환하여 리턴함

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = {};

    for (let i = 0; i < strs.length; i++) {
        const target = strs[i];
        const sortTarget = target.split('').sort().join('');

        if (!map[sortTarget]) {
            map[sortTarget] = [target];
        } else {
            map[sortTarget].push(target);
        }
    }

    return Object.values(map);
};

---

결론

주의할 점은 key를 정렬된 문자열로 만들기 위해 sort하는 부분을 조심해야 함

현재는 하나의 문자만 비교를 하기 때문에 .sort()를 사용 (.sort()만 호출하면 배열의 모든 요소를 문자열 -> 유니코드 값 순서로 정렬)

만약 하나의 문자가 아닌 '100'과 같은 문자가 있다면 .sort((a, b) => a.localeCompare(b))를 통해 정렬해야 함

(그냥 .sort()할 경우 100은 1로 판단하여 정렬되어 제대로 정렬이 안됨)

 

시간 복잡도 : O(nlogn)