Leetcode 49. Group Anagrams

49. Group Anagrams

 

Medium

 

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

 

Constraints:

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

---

입력값은 문자열로 구성된 배열입니다.

해쉬를 이용해 풀어보겠습니다.

우선 Map 오브젝트를 생성합니다.

forEach 함수를 이용해 문자열 배열을 순회하면서 letters를 만들어 줍니다.

디버그 툴을 이용해 forEach 함수 내에서 hash맵의 변화를 관찰해 보겠습니다.

 

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const hash = new Map();
    strs.forEach(str => {
        let letters = str.split('').sort();
        hash[letters] ? hash[letters].push(str) : hash[letters] = [str];
    })

    const keys = Object.keys(hash);
    const values = keys.map(value => hash[value]);
    return values;
};

 

우선 빈 해쉬가 생성되었습니다.

 

첫번째 단어가 추가된 모습입니다.

두번째 단어가 추가된 모습입니다.

세번째 단어 루프를 돌고 있습니다. tan 은 eat, tea 와 anagram 이 아니므로 별도의 키가 생성될 것입니다.

아래 표는 예제 1의 3번째 단어(tan)까지 루프를 돌았을 때의 해쉬맵의 상태입니다. 

 

Key	Value
['a', 'e', 't']	'eat', 'tea'
['a', 'n', 't']	'tan'

str.split('').sort();

표와 같이 키 값은 sort를 통해 정렬이 되어 단어 순서에 상관없이 anagram 이면 같은 키를 가지게 됩니다.

우리가 관심이 있는 것은 value 로 나중에 모든 밸류가 구해진 다음 array로 리턴을 해주게 되면 됩니다.

 

forEach 함수가 끝난 후 해쉬테이블의 모습입니다.

Object.keys(hash)

를 이용해 키값만 빼 준 후

const values = keys.map(value => hash[value])

빼준 키값을 이용해 es6 람다식을 이용해서 value 값만 빼서 values를 만들어 주고 리턴해줍니다.

위 값은 아래와 모두 동일합니다.

ES6 이전 map함수 사용법

ES6 람다식 적용

코드가 한줄일때 코드블럭 생략

인자가 하나일때 () 생략

---

해쉬 이용 풀이 성능

정상적으로 잘 동작하는 것을 확인했습니다.

이상으로 그룹 아나그램 릿코드 풀이를 마치겠습니다.

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.