题目

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

示例：

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

题解思路

  • 方法一：遍历数组，将当前遍历到的元素跟剩下的其他元素进行对比，符合要求（字母相同，但排列不同）的归类到同一组，不符合要求的单独归类一组。重点就是如何判断当前元素是否符合要求，是否有对应可以归类 的数组。字母相同，但排列不同，可知，两个元素length相同，并且A字符串里面的所有字符都应该在B字符串里能找到相同的元素，同时B字符串里面的所有字符也都应该在A字符串里能找到相同的元素。并且当前元素没有被归类过。这样的话，如果，已归类的数组里没有找到与该元素字母相同，但排列不同的元素，那就单独归类到一组，等待其他元素加入，否则，就把该元素加入到符合要求的那一组中去。

    弊端：多次循环遍历数组实现，效率较低，执行时间慢。

  • 方法二：看到字母相同，但排列不同这几个字眼，应该能立马想到既然是字母都相同，那我让所有元素都按字母排序好再进行比较，不就能直接判断两个元素是否相等了吗，相等的话push到同一个归类数组里，否则单独给他push到一个归类数组，等待下一个元素加入。但是你排序后，要返回的还是排序前的字母。所以，有没有一种数据结构既能保存两种状态？相比较于Object，Map更能轻松的获取键值对和判断是否存在某个值。这道题用Map和排序的思路可以很轻松的实现。并且代码量较少。

代码实现

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = function(strs) {
    let results = []; // 结果数组
    const includesEl = []; // 已经归组的元素
    for(let i = 0; i < strs.length; i++) {
        const tempArr = []; // 临时的分组数组
        if (includesEl.findIndex(item => item.value === strs[i]) === -1 || ((includesEl.findIndex(item => item.value === strs[i]) !== -1) && includesEl.findIndex(item => item.index === i) === -1)) { // 不在已经归组的元素里面或者在已经归组的元素里面但是只是值一样，不是同一个元素
            tempArr.push(strs[i]);
            includesEl.push({value: strs[i], index: i});
        }
        for(let j = i + 1; j < strs.length; j++) {
            if (strs[i].length === strs[j].length) {
                const iArr = strs[i].split('');
                const jArr = strs[j].split('');
                const flag = iArr.every(char => {
                    return jArr.includes(char) && jArr.filter(item => item === char).length === iArr.filter(item => item === char).length;
                })
                if (flag && (includesEl.findIndex(item => item.value === strs[j]) === -1 || ((includesEl.findIndex(item => item.value === strs[j]) !== -1) && includesEl.findIndex(item => item.index === j) === -1))) {
                    tempArr.push(strs[j]);
                    includesEl.push({value: strs[j], index: j});
                }
            }
        }
        results.push(tempArr);
    }
    results = results.filter(i => i.length);
    return results;
};

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = function(strs) {
    let map = new Map();
    strs.forEach(item => {
        const sortItem = item.split('').sort().join(''); // 排序
        if (map.has(sortItem)) { // 如果已经有相同的字母，把他归类到同一个数组
            map.get(sortItem).push(item);
        } else {
            map.set(sortItem, [item]); // 把排序后的当key，原数据当value存入
        }
    })
    return [...map.values()];
};