The title

Write a way to sort an array of strings and group all the inflections together. An anagram is a string of characters with the same letters, but arranged differently.

Example:

Input: [" eat ", "tea", "tan", "ate" and "NAT" and "bat"], output: [[" ate ", "eat", "tea"], [" NAT ", "tan"], [" bat "]]

Description:

All input is lowercase. It doesn’t matter what order the answers are printed in.

Antithesis thought

  • Method 1: traverse the array and compare the currently traverse elements with the rest of the elements. Those that meet the requirements (the same letters, but different arrangements) are classified into the same group, while those that do not meet the requirements are classified into a separate group. The point is how to determine whether the current element meets the requirements, whether there is a corresponding array that can be categorized. Same letters, but different arrangement, so they have the same length, and all of the characters in string A should have the same element in string B, and all of the characters in string B should have the same element in string A. And the current element is not classified. That way, if you don’t find any other elements in the same letter but in a different arrangement, you put them in a separate group and wait for other elements to join you. If you don’t, you put them in the same group.

    Disadvantages: the implementation of multiple cycle traversing group, low efficiency, slow execution time.

  • Method 2: SeeThe letters are the same, but the arrangement is differentThese words, you should immediately think that since they’re all the same letters, if I put all the elements in alphabetical order and then compare them, I’ll be able to directly determine whether they’re equal or not. If they’re equalpushPut it in the same category array, or give it to it alonepushGo to a categorised array and wait for the next element to be added. But when you sort it, you still have to return the letter that you started with. So, is there a data structure that can hold both states? Compared with Object, Map can easily obtain key-value pairs and determine the existence of a value. This problem can be easily implemented using Map and sorting ideas. And less code.

Code implementation

Method one:

/** * @param {string[]} strs * @return {string[][]} */ const groupAnagrams = function(strs) { let results = []; // Result array const includesTestesel = []; // For (let I = 0; i < strs.length; i++) { const tempArr = []; / / if temporary grouping array (includesEl findIndex (item = > item. The value = = = STRS [I]) = = = 1 | | ((includesEl. FindIndex (item = > item. The value === strs[i]) ! == -1) && IncludeSesel. findIndex(item = BB0 item.index === = -1)) {// Not in the elements that have been grouped but the values are the same, Not the same element tempar.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; };

Method 2:

/** * @param {string[]} strs * @return {string[][]} */ const groupAnagrams = function(strs) { let map = new Map(); strs.forEach(item => { const sortItem = item.split('').sort().join(''); // Sort if (map.has(sortItem)) {// Sort if (map.has(sortItem)) {// Sort it into the same array map.get(sortItem).push(item); } else { map.set(sortItem, [item]); }}) return [...map.values()]; };