49. 字母异位词分组

[bt2ee]

题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

示例 1:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

解题

简单题目的翻版，依然是桶排序的思想

解题方法

排序法

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const table = {}
    function sort(str){
        return str.split("").sort().join("");
    }
    for(let i = 0; i < strs.length;i++) {
        const str = strs[i]
        const sortStr = sort(str)
        if(table[sortStr]) {
            table[sortStr].push(str)
        } else {
             table[sortStr] = [str]
        }
    }
    return Object.values(table)
};

二进制

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const hashTable = {};
  for (let str of strs) {
    let arr = new Array(26).fill(0)
    for (let i = 0; i < str.length; i++) {
      arr[str.codePointAt(i) - "a".codePointAt()]++;
    }
    const key = arr.join();
    if (hashTable[key]) {
      hashTable[key].push(str);
    } else {
      hashTable[key] = [str];
    }
  }
  return Object.values(hashTable);
};

质数法

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const hashTable = {};
  for (let str of strs) {
    const hash = str.split("").reduce((sum, s) => {
      return sum * [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103][s.charCodeAt(0) - 97]
    }, 1);
    hashTable[hash] ? hashTable[hash].push(str) : hashTable[hash] = [str];
  }
  return Object.values(hashTable);
};

关联题

242. 有效的字母异位词(简单)