Anagrams finder in javascript

Question

I am supposed to write a program in JavaScript to find all the anagrams within a series of words provided. e.g.: "monk, konm, nkom, bbc, cbb, dell, ledl, llde" The output should be categorised into rows: 1. monk konm, nkom; 2. bbc cbb; 3. dell ledl, llde;

I already sorted them into alphabetical order i.e.: "kmno kmno bbc bbc dell dell" and put them into an array.

However I am stuck in comparing and finding the matching anagram within the array.

Any help will be greatly appreciated.

Answer 1

I know this is an ancient post...but I just recently got nailed during an interview on this one. So, here is my 'new & improved' answer:

var AnagramStringMiningExample = function () {

/* Author: Dennis Baughn
*  This has also been posted at: 
*  http://stackoverflow.com/questions/909449/anagrams-finder-in-javascript/5642437#5642437

*  Free, private members of the closure and anonymous, innner function
*  We will be building a hashtable for anagrams found, with the key 
*  being the alphabetical char sort (see sortCharArray()) 
*  that the anagrams all have in common. 
*/
    var dHash = {};

    var sortCharArray = function(word) {
        return word.split("").sort().join("");
    };

/* End free, private members for the closure and anonymous, innner function */

/* This goes through the dictionary entries. 
 *  finds the anagrams (if any) for each word,
 *  and then populates them in the hashtable. 
 *  Everything strictly local gets de-allocated 
 *  so as not to pollute the closure with 'junk DNA'.
*/
    (function() {
       /* 'dictionary' referring to English dictionary entries. For a real 
        *  English language dictionary, we could be looking at 20,000+ words, so 
        *  an array instead of a string would be needed.
        */
       var dictionaryEntries = "buddy,pan,nap,toot,toto,anestri,asterin,eranist,nastier,ratines,resiant,restain,retains,retinas,retsina,sainter,stainer,starnie,stearin";
       /* This could probably be refactored better.  
        * It creates the actual hashtable entries. */
       var populateDictionaryHash = function(keyword, newWord) {
          var anagrams = dHash[keyword];
          if (anagrams && anagrams.indexOf(newWord) < 0) 
            dHash[keyword] = (anagrams+','+newWord);
          else dHash[keyword] = newWord;
       };

       var words = dictionaryEntries.split(",");

       /* Old School answer, brute force
       for (var i = words.length - 1; i >= 0; i--) {
        var firstWord = words[i];
        var sortedFirst = sortCharArray(firstWord);
        for (var k = words.length - 1; k >= 0; k--) {
               var secondWord = words[k];
           if (i === k) continue;
            var sortedSecond = sortCharArray(secondWord);
            if (sortedFirst === sortedSecond)   
                       populateDictionaryHash(sortedFirst, secondWord);
        }
       }/*

        /*Better Method for JS, using JS Array.reduce(callback) with scope binding on callback function */
        words.reduce(function (prev, cur, index, array) { 
            var sortedFirst = this.sortCharArray(prev);
            var sortedSecond = this.sortCharArray(cur); 
            if (sortedFirst === sortedSecond) {
                var anagrams = this.dHash[sortedFirst];
                if (anagrams && anagrams.indexOf(cur) < 0) 
                   this.dHash[sortedFirst] = (anagrams + ',' + cur);
                else 
                   this.dHash[sortedFirst] = prev + ','+ cur;                    
            }
            return cur;
        }.bind(this));
    }());

    /* return in a nice, tightly-scoped closure the actual function 
     *  to search for any anagrams for searchword provided in args and render results. 
    */
    return function(searchWord) {
       var keyToSearch = sortCharArray(searchWord);
       document.writeln('<p>');
       if (dHash.hasOwnProperty(keyToSearch)) {
        var anagrams = dHash[keyToSearch];
        document.writeln(searchWord + ' is part of a collection of '+anagrams.split(',').length+' anagrams: ' + anagrams+'.');
       } else document.writeln(searchWord + ' does not have anagrams.');
       document.writeln('<\/p>');
    };
};

Here is how it executes:

var checkForAnagrams = new AnagramStringMiningExample();
checkForAnagrams('toot');
checkForAnagrams('pan');
checkForAnagrams('retinas');
checkForAnagrams('buddy');

Here is the output of the above:

toot is part of a collection of 2 anagrams: toto,toot.

pan is part of a collection of 2 anagrams: nap,pan.

retinas is part of a collection of 14 anagrams: stearin,anestri,asterin,eranist,nastier,ratines,resiant,restain,retains,retinas,retsina,sainter,stainer,starnie.

buddy does not have anagrams.

Answer 2

Here is my solution which addresses a test case where the input strings which are not anagrams, can be removed from the output. Hence the output contains only the anagram strings. Hope this is helpful.

/**
 * Anagram Finder
 * @params {array} wordArray
 * @return {object}
 */
function filterAnagram(wordArray) {
  let outHash = {};
  for ([index, word] of wordArray.entries()) {
    let w = word.split("").sort().join("");
    outHash[w] = !outHash[w] ? [word] : outHash[w].concat(word);
  }
  let filteredObject = Object.keys(outHash).reduce(function(r, e) {
    if (Object.values(outHash).filter(v => v.length > 1).includes(outHash[e])) r[e] = outHash[e]
    return r;
  }, {});

  return filteredObject;
}

console.log(filterAnagram(['monk', 'yzx','konm', 'aaa', 'ledl', 'bbc', 'cbb', 'dell', 'onkm']));

Answer 3

var check=true;
var str="cleartrip";
var str1="tripclear";
if(str.length!=str1.length){
console.log("Not an anagram");

check=false;
}
console.log(str.split("").sort());
console.log("----------"+str.split("").sort().join(''));
if(check){
if((str.split("").sort().join(''))===((str1.split("").sort().join('')))){
console.log("Anagram")
}
else{
console.log("not a anagram");
}
}

Answer 4

I had this question in an interview. Given an array of words ['cat', 'dog', 'tac', 'god', 'act'], return an array with all the anagrams grouped together. Makes sure the anagrams are unique.

var arr = ['cat', 'dog', 'tac', 'god', 'act'];

var allAnagrams = function(arr) {
    var anagrams = {};
    arr.forEach(function(str) {
        var recurse = function(ana, str) {
            if (str === '') 
                anagrams[ana] = 1;
            for (var i = 0; i < str.length; i++)
                recurse(ana + str[i], str.slice(0, i) + str.slice(i + 1));
        };
        recurse('', str);
    });
    return Object.keys(anagrams);
}

console.log(allAnagrams(arr));
//["cat", "cta", "act", "atc", "tca", "tac", "dog", "dgo", "odg", "ogd", "gdo", "god"]

Answer 5

i have recently faced this in the coding interview, here is my solution.

    function group_anagrams(arr) {
      let   sortedArr = arr.map(item => item.split('').sort().join(''));
      let setArr = new Set(sortedArr);
      let reducedObj = {};
      for (let setItem of setArr) {
        let indexArr = sortedArr.reduce((acc, cur, index) => {
          if (setItem === cur) {
            acc.push(index);
          }
          return acc;
        }, []);
        reducedObj[setItem] = indexArr;
      }
      let finalArr = [];
      for (let reduceItem in reducedObj) {
        finalArr.push(reducedObj[reduceItem].map(item => arr[item]));
      }
      return finalArr;
    }
    group_anagrams(['car','cra','rca', 'cheese','ab','ba']);

output will be like

[
  ["car", "cra", "rca"],
  ["cheese"],
  ["ab", "ba"]
]

Answer 6

Here is my take:

var input = "monk, konm, bbc, cbb, dell, ledl";
var words = input.split(", ");

for ( var i = 0; i < words.length; i++) {

    var word = words[i];
    var alphabetical = word.split("").sort().join("");

    for (var j = 0; j < words.length; j++) {

        if (i === j) {
            continue;
        }

        var other = words[j];
        if(alphabetical === other.split("").sort().join("")){
            console.log(word + " - " + other + " (" + i + ", " + j + ")");
        }
    }
}

where the output would be (the word, the match and the index of both):

monk - konm (0, 1)
konm - monk (1, 0)
bbc - cbb (2, 3)
cbb - bbc (3, 2)
dell - ledl (4, 5)
ledl - dell (5, 4)

To get the characters in the in alphabetical order, I used split("") ot get an array, called sort() and used join("") to get a string from the array.