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

Simple Solution

function anagrams(stringA, stringB) {
    return cleanString(stringA) === cleanString(stringB);
}

function cleanString(str) {
    return str.replace(/[^\w]/g).toLowerCase().split('').sort().join()
}   

anagrams('monk','konm')

If it is anagrams function will return true otherwise false

Answer 2

I have an easy example

function isAnagram(strFirst, strSecond) {

 if(strFirst.length != strSecond.length)
       return false;

 var tempString1 = strFirst.toLowerCase();
 var tempString2 = strSecond.toLowerCase();

 var matched = true ;
 var cnt = 0;
 while(tempString1.length){
    if(tempString2.length < 1)
        break;
    if(tempString2.indexOf(tempString1[cnt]) > -1 )
        tempString2 = tempString2.replace(tempString1[cnt],'');
    else
        return false;

    cnt++;
 }

 return matched ;

 }

Calling function will be isAnagram("Army",Mary); Function will return true or false

Answer 3

My solution to this old post:

// Words to match
var words = ["dell", "ledl", "abc", "cba"],
    map = {};

//Normalize all the words 
var normalizedWords = words.map( function( word ){
  return word.split('').sort().join('');
});

//Create a map: normalizedWord -> real word(s)
normalizedWords.forEach( function ( normalizedWord, index){
  map[normalizedWord] = map[normalizedWord] || [];
  map[normalizedWord].push( words[index] );
});

//All entries in the map with an array with size > 1 are anagrams
Object.keys( map ).forEach( function( normalizedWord , index  ){
  var combinations = map[normalizedWord];
  if( combinations.length > 1 ){
    console.log( index + ". " + combinations.join(' ') );
  }
});

Basically I normalize every word by sorting its characters so stackoverflow would be acefkloorstvw, build a map between normalized words and the original words, determine which normalized word has more than 1 word attached to it -> That's an anagram.

Answer 4

Another solution for isAnagram using reduce

const checkAnagram = (orig, test) => {
  return orig.length === test.length 
    && orig.split('').reduce(
      (acc, item) => {
        let index = acc.indexOf(item);
        if (index >= 0) {
          acc.splice(index, 1);
          return acc;
        }
        throw new Error('Not an anagram');
      },
      test.split('')
    ).length === 0;
};

const isAnagram = (tester, orig, test) => {
  try {
    return tester(orig, test);  
  } catch (e) {
    return false;
  }
}

console.log(isAnagram(checkAnagram, '867443', '473846'));
console.log(isAnagram(checkAnagram, '867443', '473846'));
console.log(isAnagram(checkAnagram, '867443', '475846'));

Answer 5

My solution has more code, but it avoids using .sort(), so I think this solution has less time complexity. Instead it makes a hash out of every word and compares the hashes:

const wordToHash = word => {
  const hash = {};
  // Make all lower case and remove spaces
  [...word.toLowerCase().replace(/ /g, '')].forEach(letter => hash[letter] ? hash[letter] += 1 : hash[letter] = 1);
  return hash;
}
const hashesEqual = (obj1, obj2) => {
  const keys1 = Object.keys(obj1), keys2 = Object.keys(obj2);
  let match = true;
  if(keys1.length !== keys2.length) return false;
  for(const key in keys1) { if(obj1[key] !== obj2[key]) match = false; break; }
  return match;
}
const checkAnagrams = (word1, word2) => {
  const hash1 = wordToHash(word1), hash2 = wordToHash(word2);
  return hashesEqual(hash1, hash2);
}
console.log( checkAnagrams("Dormitory", "Dirty room") );

Answer 6

I worked through a similar question to this today and wanted to share the results of my work. I was focused on just detecting the anagram so processing the list of words was not part of my exercise but this algorithm should provide a highly performant way to detect an anagram between two words.

function anagram(s1, s2){
  if (s1.length !== s2.length) {
    // not the same length, can't be anagram
    return false;
  }
  if (s1 === s2) {
    // same string must be anagram
    return true;
  }

  var c = '',
    i = 0,
    limit = s1.length,
    match = 0,
    idx;
  while(i < s1.length){
    // chomp the next character
    c = s1.substr(i++, 1);
    // find it in the second string
    idx = s2.indexOf(c);
    if (idx > -1) {
      // found it, add to the match
      match++;
      // assign the second string to remove the character we just matched
      s2 = s2.substr(0, idx) + s2.substr(idx + 1);
    } else {
      // not found, not the same
      return false;
    }
  }
  return match === s1.length;
}

I think technically is can be solved like this:

function anagram(s1, s2){
  return s1.split("").sort().join("") === s2.split("").sort().join("");
}

The reason I chose the earlier approach is that it is more performant for larger strings since you don't need to sort either string, convert to an array or loop through the entire string if any possible failure case is detected.