#49 Group Anagrams

善用英文字母只有 26 的優勢

Given an array of strings strs, group the strings that are anagrams of each other. The result can be returned in any order.

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

Input

• strs: string[]: An array of strings

Examples

Input: strs = ["abc","bca","cab","xyz","zyx"]
Output: [["abc","bca","cab"],["xyz","zyx"]]
Explanation: Two anagram groups: 'abc'-'bca'-'cab' and 'xyz'-'zyx'.

Input: strs = ["rat","tar","art","car","arc"]
Output: [["arc","car"],["art","rat","tar"]]
Explanation: Two anagram groups: 'car'-'arc' and 'rat'-'tar'-'art'.

Input: strs = ["kxac","swavb","lmq","lvhc","sjey"]
Output: [["kxac"],["lmq"],["lvhc"],["sjey"],["swavb"]]
Explanation: Each word has no anagram in the list.

怎麼解

• 把 "abc" 用成 [1, 1, 1, 0,.....] 所以 'abc" 跟 "bca" 會是一樣的 key

• 注意 edge case 例如 "aab" 會是 [2, 1, 0, 0...]

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
export default function anagramGroups(strs) {
  let len = strs.length;
  if (len === 0) return [];

  let lookup = new Map();
  let result = [];

  for (let i = 0; i < len; i++) {
    let key = transformFromAlphabetToCollections(strs[i]);
    if (lookup.has(key)) {
      lookup.set(key, [...lookup.get(key), strs[i]]);
    } else {
      lookup.set(key, [strs[i]]);
    }
    // [1,1,1,....]
  }

  lookup.values().forEach((val) => result.push(val));

  return result;
}

// "abc"
function transformFromAlphabetToCollections(str) {
  let result = Array.from({ length: 26 }, () => 0);
  for (let i = 0; i < str.length; i++) {
    result[str[i].charCodeAt() - 97] += 1;
  }

  return JSON.stringify(result);
}