字母异位词分组

概要： 中等题，给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例：

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

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

心路历程

一开始，我接触这题直接想偏了，想的是，对strs进行遍历，拿到当前的字符串，然后转换成数组，然后遍历map的key，然后找key为当前字符串的异位词，找到则在这个key对应的数组后增加当前字符串，没有则用当前字符串为key创建个数组，也就是用map存储遍历过的字符串和对应的字母异位词数组，最后遍历map提取出结果。

我这思路是有问题的，且不说，判断好不好判断，光是使用循环就用了好多次了。

这到题其实可以简化为如何判断两个字符串是不是异位词，解决了这个，就简单多了。

排序比较法

用replace一个一个替换，在判断length？用双循环比对？转换数组在排序在比较？最后一个是最适合的，不用考虑排序规则是什么，只要都用同一个规则就行。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map();
  const result = [];
  for (let i = 0; i < strs.length; i++) {
    const str = strs[i];
    const key = str.split("").sort().join("");
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(str);
  }
  map.forEach((value, key) => {
    result.push(value);
  });
  return result;
};

上面这种解放就是利用排序来判断两个字符串是不是异位词。当然也可以不用 result数组，直接Array.from(map.values())也可以。

质数相乘法

网上看到的解题方案，不得不说真牛掰，思路就是先创建含有26位质数的数组，再用charCodeAt将一个一个字符转换成 UTF-16 码元值，而这个码元值减去97就得到了0~25的索引，再用这个索引取得对应的质数再累乘。利用一个数字不为质数的话，那可以唯一分解成有限个质数的乘积这一定理，取得一个代表这个字符的唯一数字，如果数字相等那就是异位词。

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以，质数是合数的基础，没有质数就没有合数。这也说明了前面所提到的质数在数论中有着重要地位。历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。

var groupAnagrams = function (strs) {
  var h = new Map(),
    prime = [
      2, 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,
    ];
  for (var i = 0; i < strs.length; i++) {
    let sum = 1; // 初始化乘法单位元，空字符串的最终sum为1," "最终为NaN（依然可以为key）
    for (var j = 0; j < strs[i].length; j++) {
      sum *= prime[strs[i].charCodeAt(j) - 97];
    }
    h.has(sum) ? h.get(sum).push(strs[i]) : h.set(sum, [strs[i]]);
  }
  return Array.from(h.values());
};

标记暴力解放

网上看到的，虽说用时最多，但是多看看，开拓视野，对自己没坏处。这个解放就是先搞出排序了字符串的数组，然后双循环拿异位词，并标记已经遍历过的字符串。

var groupAnagrams = function (strs) {
  let len = strs.length;
  // 排序一下数组中每个字符串的顺序
  let temp = [];
  for (let str of strs) {
    temp.push(str.split("").sort().join(""));
  }
  // 结果数组
  let ans = [];
  for (let i = 0; i < len; i++) {
    // 为"0",说明已经遍历对比过了
    if (temp[i] === "0") {
      continue;
    }
    let cur = [];
    // 先把当前的扔进去
    cur.push(strs[i]);
    for (let j = i + 1; j < len; j++) {
      if (temp[i] === temp[j] && temp[i] != "0") {
        cur.push(strs[j]);
        // 标识为已对比
        temp[j] = "0";
      }
    }
    ans.push(cur);
  }
  return ans;
};

最终代码

var groupAnagrams = function (strs) {
  var h = new Map(),
    prime = [
      2, 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,
    ];
  for (var i = 0; i < strs.length; i++) {
    let sum = 1; // 初始化乘法单位元，空字符串的最终sum为1," "最终为NaN（依然可以为key）
    for (var j = 0; j < strs[i].length; j++) {
      sum *= prime[strs[i].charCodeAt(j) - 97];
    }
    h.has(sum) ? h.get(sum).push(strs[i]) : h.set(sum, [strs[i]]);
  }
  return Array.from(h.values());
};

参考链接

• [字母异位词分组](49. 字母异位词分组 - 力扣（LeetCode）)