LeetCode - 49. Group Anagrams

Thoughts:

I can use hash map to solve this problem. The value is the array of containing same anagram in original array. And the key a string that contains the count of each alphabet. The time complexity will be O(n²).

Thoughts visuzlization:

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

first, iterate the array...
and make a default array that
the index is alphabet (0 ~ 25 -> a ~ z)
each element is the count of alphabet (now they are all 0)
for example, "big" -> [0, 1, 0, 0, 0, 0, 1, 0, 1, ...]
                       a  b  c  d  e  f  g  h  i  ...

second, convert the array to string
for example "big" -> "010000101..."
BUT, need to add a special character to separate each alphabet,
to avoid count is bigger than 9,
for example, "bbbbbbbbbbig" -> [0, 10, 0, 0, 0, 0, 1, 0, 1, ...]
                                a   b  c  d  e  f  g  h  i  ...
if converting the array with the empty string for separating each alphabet count,
then the result will be "0100000101..."
I can't find each count belongs to which alphabet in this situation...
so need to add a special character to separate each alphabet.
for example, add '#' as the special character, make the result to "0#10#0#0#0#0#1#0#1#..."

In the end, the map will be like this...
map = {
  "0#10#0#0#0#0#1#0#1#...": ["bbbbbbbbbbig", "bbbibbbgbbbb", "bbbigbbbbbbb", ...],
  ...
}
and we just need to get the values of the map.

Code:

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map();
  const answer = [];
  for (let str of strs) {
    const alphabetCounts = new Array(26).fill(0);
    for (let c of str) {
      alphabetCounts[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    const key = alphabetCounts.join('#');
    map.set(key, [...(map.get(key) || []), str]);
  }
  return [...map.values()];
};

Reference

Original link