JavaScript group anagram performance

Question

I created an algorithm to create lists of anagrams

The input is ["eat", "tea", "tan", "ate", "nat", "bat"]

Then, the output should be: [["eat","tea","ate"],["tan","nat"],["bat"]]

Each array is words that are anagram.

My solution is:

function group(input) {
 let result = [];
 if(input.length === 0){
 return result;
 }
 for(let i=0; i<input.length; i++){
 let check = true;
 for(let j=0; j<result.length; j++){
 if(result[j].includes(input[i])){
 check = false;
 }
 }
 if(check){
 result.push(checkAnagrams(input, i)); 
 }
 }
 return result;
}
function checkAnagrams(aStr, i){
 let anagrams = [];
 anagrams.push(aStr[i]);
 for(let j=0; j<aStr.length; j++){
 if(i !== j){
 if(isAnagram(aStr[i], aStr[j])){
 anagrams.push(aStr[j]);
 }
 }
 }
 return anagrams;
}
function isAnagram(str1, str2) {
 // split => string into array
 // sort => sort the array
 // join => string to array
 // trim => remove any space
 const string1 = str1.split("").sort().join().trim();
 const string2 = str2.split("").sort().join().trim();
 if(string1 === string2){
 return true;
 } 
 return false; 
}

I know it works, but I was wondering if there is a better way to implement it.

Thanks

Answer 1

Based on the code written by dariosicily I made a bit of changes to it.

const key could be declared outside with let, it improves a bit the performance. The inside of the loop, could be changed by:

function anagrams(input) {
 const map = new Map();
 let key;
 for (let i = 0; i < input.length; ++i) {
 if (map.has(key = [...input[i]].sort().join(''))) 
 map.get(key).push(input[i]);
 else map.set(key, [input[i]]);
 }
 return [...map.values()];
}

The assignment of variables has a quite notorious performance impact (when the input is great enough).

Note: I thought of writing it as a comment to dario but it was big.

• dariosicily: Thanks for your hints.
• RoToRa: Could you provide sources to this claim? Conceptionally a const should be preferred here over let because its a different key in each loop and not a single key that is changing. Considering the complexity of the logic inside the loop, I doubt that "reusing" a variable changes the performance noticeably.

Answer 2

Welcome to Code Review, the complexity of your code can be reduced using a Map object having as keys sorted lexicographically strings and as values arrays of their anagrams. For example you will have the following couples key - value starting from your input:

key = "aet" value = ["eat","tea","ate"]
key = "ant" value = ["tan","nat"]
key = "abt" value = ["bat"]

So you can define a function anagrams like this:

function anagrams(input) {
 const map = new Map();
 for (let i = 0; i < input.length; ++i) {
 const key = [...input[i]].sort().join('');
 const value = map.has(key) ? map.get(key) : [];
 value.push(input[i]);
 map.set(key, value);
 }
 return [...map.values()];
}
/*below it will print the expected result*/
console.log(anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])); 

I just used the Spread operator to expand the string input[i] to array of characters and after I sort it to obtain the corrisponding key in the map. After I add it to the array of strings associated to the key and finally I return the map values as an array.

Note: I'm a javascript beginner so every hint or criticism about my answer is highly appreciated.

• KooiInc: Consider not using spread
• dariosicily: @KooiInc Thanks for your advice and the link, I will use spread just for simple exercises like this; it is quite surprising to find a 10x difference between one construct and another one applied to the same task.