49. Group Anagrams

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

같은 아나그램(들어있는 문자가 똑같은 문자를 아나그램이라 한다)끼리 묶은 새 배열을 반환하는 문제이다.

Solution

Encode anagram info and use hash

문자열이 아나그램인지 비교하는 방법으로 가장 쉬운방법은 각 문자가 몇개씩 들어있는지 나타내는 배열을 이용하는 것이다. 예를들어 'abc'와 'bca'는 [1,1,1,0,0,0,...] 의 동일한 배열을 가지고 둘을 비교하면 아나그램여부를 판단할 수 있다. 그러나 이러한 방법은 비교대상의 아나그램이 n개가 존재할 경우 O(n)의 비교를 통해 같은 그룹인지 판단하게 된다.

같은 속성을 좀 더 효율적으로 그룹화 하기 위해 우리는 hash를 이용한다. 해시함수는 각각을 전부 비교하지 않고 O(1)의 시간으로 같은 속성을 찾아낼 수 있다. 위의 아나그램 속성([1,1,1,0,...]) 을 hash의 key로 표현할 수 있다면 같은 아나그램 그룹인지 판단하는데 O(1)의 시간이 들게된다. 아나그램 속성배열은 크기가 그렇게 크지 않기 때문에 이 형태를 key로 사용하는 방법을 생각해보았다. 'abc'는 'a1b1c1'의 형태로 인코딩을 해 사용할 수 있다. 같은 아나그램은 같은 키를 가지게 되는 것이다.

위와 같은 방법으로 문자열을 아나그램 키로 인코딩하고 키에 따라 Map으로 그룹화를 한다면 효율적으로 문제를 해결할 수 있다.
인코딩하는 시간: O(n) (n: 문자열 길이, 최대 100)
인코딩된 문자열을 Map에 추가하는 시간: O(m) (m: 문자열 개수)
총: O(n*m) <= O(100m)

Algorithm

• 문자열을 아나그램 키로 인코딩한다
• 인코딩하는 방법은 배열을 통해 각 문자의 개수를 파악하고 0이 아닌 배열을 해당 문자와 함께 추가한다. ('abc' => 'a1b1c1')
• 인코딩 된 아나그램 key를 통해 Map에 추가한다. (AnagramKey => String)
• 모든 문자열을 Map에 추가한 후 Map의 values()를 호출해 결과를 반환한다.

var groupAnagrams = function(strs) {
  // Make anagram key (abc => 'a1b1c1')
  // Make map that has anagram key as key ('a1b1c1' => ['abc', 'bac'])
  const aCode = 'a'.charCodeAt(0); // 97
  const alphabet = 'abcdefghijklmnopqrstuvwxyz'
  const myMap = new Map();
  
  // Get anagram key from string
  const getAnagramKey = (str) => {
    let result = '';
    const alphaArr = new Array(26).fill(0);
    for (let letter of str) {
      alphaArr[letter.charCodeAt(0) - aCode]++;
    }
    alphaArr.forEach((el, idx) => {
      if (el > 0) result += alphabet[idx] + el; // add 'alphabet+count' to result
    });
    return result;
    // return anagramKey that has alphabet counts
  }
  
  for (let str of strs) {
    const strKey = getAnagramKey(str);
    myMap.has(strKey) ? myMap.get(strKey).push(str) : myMap.set(strKey, [str]);
  }
  
  return [...myMap.values()];
  // change myMap to array and return
};