关于数据结构和算法:码不停题算法篇变位词组

题目

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

示例：

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

阐明：

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

题解思路

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

  弊病：屡次循环遍历数组实现，效率较低，执行工夫慢。

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

代码实现

办法一：

/**
 * @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;
};

办法二：

/**
 * @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()];
};