Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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:

STRS = [“”] output: [[“”]]

Example 3:

STRS = [“a”] output: [[“a”]]

 

Tip:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i]Contains only lowercase letters

Train of thought

Prime Numbers

Their thinking

  • Fundamental theorem of arithmetic
    • Any natural number N greater than 1, if N is not prime, then N canThe onlyDecomposed into a product of finite prime numbers
  • [a, z]Unicode encoding -97 =[0, 25]The corresponding26 prime Numbers. Each letter stands forPrime NumberstheThe product ofRepresentation string
  • Commutative law of multiplicationIgnore alphabetical order.Fundamental theorem of arithmeticGuarantee that different primes or different numbers of the same prime number, productThe only

code

Map

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++) {
        for(var j = 0, sum = 1; 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())
};
Copy the code

Object

var groupAnagrams = function(strs) {
    var h = Object.create(null), 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++) {
        for(var j = 0, sum = 1; j < strs[i].length; j++) 
            sum *= prime[strs[i][j].charCodeAt() - 97]
        h[sum] ? h[sum].push(strs[i]) : h[sum] = [strs[i]]
    }
    return Object.values(h)
};
Copy the code

link

  • Odd number sieving is recommended for prime number generation
var getPrimes = function(n) {// getPrimes(102) can get 26 primes
    var isCom= new Uint8Array(n), b = Math.sqrt(n), r = n > 2 ? [2] : [], t
    for(var i = 3; i < n; i += 2) {
        if(! isCom[i]) { r.push(i)if (i <= b) for(var j = i; (t = i * j) < n; j += 2) isCom[t] = 1}}return r
};
Copy the code

Sort

Their thinking

  • SortIgnore arguments and press elementsUnicode siteSort, that is,UnicodeAscending order

code

Map

var groupAnagrams = function(strs) {
    var h = new Map, k
    for(var i = 0; i < strs.length; i++) 
        h.has(k = strs[i].split(' ').sort().join(' '))? h.get(k).push(strs[i]) : h.set(k, [strs[i]])return Array.from(h.values())
};
Copy the code

Object

var groupAnagrams = function(strs) {
    var h = Object.create(null), k
    for(var i = 0; i < strs.length; i++) 
        h[k = strs[i].split(' ').sort().join(' ')]? h[k].push(strs[i]) : h[k] = [strs[i]]return Object.values(h)
};
Copy the code

An array of

Their thinking

  • 26The length of the array[0, 25]bitvalueCorresponding to the letter[a, z]occurrences

code

Map

var groupAnagrams = function(strs) {
    var h = new Map, sum
    for(var i = 0; i < strs.length; i++) {
        for(var j = 0, counts = new Uint8Array(26); j < strs[i].length; j++)
            counts[strs[i][j].charCodeAt() - 97]++
        h.has(sum = counts.toString()) ? h.get(sum).push(strs[i]) : h.set(sum, [strs[i]])
    }
    return Array.from(h.values())
};
Copy the code

Object

var groupAnagrams = function(strs) {
    var h = Object.create(null), sum
    for(var i = 0; i < strs.length; i++) {
        for(var j = 0, counts = new Uint8Array(26); j < strs[i].length; j++)
            counts[strs[i][j].charCodeAt() - 97]++
        h[sum = counts.toString()] ? h[sum].push(strs[i]) : h[sum] = [strs[i]]
    }
    return Object.values(h)
};
Copy the code

expand

Traversal string, byte to Unicode encoding:

  • str[i].charCodeAt(0) str.charAt(i).charCodeAt(0) str.charCodeAt(i)Who is faster?
// Setup
const ar = Array.from({length: 100}, _= > String.fromCharCode(... randArray(500.97.97 + 26)))
function randArray(len, min, max) {
    return Array.from({length: len}, _= > min + Math.random() * (max - min) | 0)}const str2unicode1 = str= > {
    let res = ' ', i = -1
    while(++i < str.length) res += str[i].charCodeAt(0)
    return res
}
const str2unicode2 = str= > {
    let res = ' ', i = -1
    while(++i < str.length) res += str.charAt(i).charCodeAt(0)
    return res
}
const str2unicode3 = str= > {
    let res = ' ', i = -1
    while(++i < str.length) res += str.charCodeAt(i)
    return res
}
// str[i].charCodeAt(0)
for(var i = 0; i < 100; i++) str2unicode1(ar[i])
// str.charAt(i).charCodeAt(0)
for(var i = 0; i < 100; i++) str2unicode2(ar[i])
// str.charCodeAt(i)
for(var i = 0; i < 100; i++) str2unicode3(ar[i])
Copy the code



str.charCodeAt(i)faster