This is the 20th day of my participation in the August More Text Challenge

preface

Today’s algorithm exercise is letter allotopic grouping, what is an allotopic? An allotropy is two different words that have exactly the same letters, like aet, eat, tae, that’s an allotropy, so let’s just do it

Topic describes

You are given an array of strings, and you are asked to combine alphabetic anagram words. The list of results can be returned in any order.

An anagram is a new word created by rearranging the letters of the source word so that all the letters in the source word are used exactly once.

 

Example 1:

Input: STRS = [” eat “, “tea”, “tan”, “ate” and “NAT” and “bat”]

Output: [[” bat “], [” NAT “, “tan”], [” ate “, “eat”, “tea”]]

Example 2:

Input: STRS = [“”]

Output: [[“]]

Example 3:

Input: STRS = [“a”]

Output: [[” a “]]

Their thinking

  • There are two possible solutions: one is to sort each word by ASCII (for example: Eat,ate,tae, aet), and then compare the sorted words to see if they are the same. If they are the same, put them in the same array
  • A better way to do this is to use an array of 26 entries, each of which is 0, to represent the 26 letters, then use ASCII-97 to match the entries in the array with the value ++, and store the 26-entry array as a key into the map
  • If there is a key in the map, then the item is stored in the value corresponding to the key, otherwise directly stored in a new key and an empty array, code into the play
/ * * *@param {string[]} strs
 * @return {string[][]}* /
var groupAnagrams = function(strs) {
    if(strs.length ===0) {// First, if the input is an empty array, return []
        return[]}const map = new Map(a)// Declare a map to store the results of the comparison
    for (const str of strs){
        const characters = Array(26).fill(0) // Generate an array of 26 entries, each 0
        for(let i=0; i<str.length; i++){let ascii = str.charCodeAt(i)-97 // ASCII 97 corresponds exactly to the subscript
            characters[ascii]++
        }
        const key = characters.join(', ') // Convert the resulting array into a string and store it in the map as a key
        if(map.has(key)){ // If the key already exists in the map, perform the following operations
            map.set(key,[...map.get(key),str])
        }else{ // If the key does not exist in the map, perform the following operations
            map.set(key,[str])
        }
    }
    const result =[]
    for(let arr of map){ // Loop through the map and insert the value into the array
        result.push(arr[1])}return result
};
Copy the code

LeetCode run result

conclusion

We compare the ASCII characters of each input word to get an array of ASCII characters. Then we compare the ASCII characters to get the result we want.