Skip to content

Instantly share code, notes, and snippets.

@garrett-green
Last active November 16, 2021 22:48
Show Gist options
  • Save garrett-green/7bcefbd7d60f45b9e80df29ab4eadfd6 to your computer and use it in GitHub Desktop.
Save garrett-green/7bcefbd7d60f45b9e80df29ab4eadfd6 to your computer and use it in GitHub Desktop.
Anagram Detector | REACTO

Prompt

You are given an array of strings only (could be words, phrases etc). Create a function to find all the anagrams within that array. The output should be an array where each element in the array is itself an array of anagrams.


Examples

const words = ['cat', 'act', 'ignore', 'a phrase', 'tape', 'pate', 'e hpsara'];
listAnagrams(words);
// [['cat', 'act'], ['a phrase', 'e hpsara'], ['tape', 'pate']]

Notice that 'ignore' does not appear in the output.


Solutions

One effective approach is:

  1. Sort each string in the array
  2. Create a hash table of these sorted strings and arrays of words that match
  3. Go through all of the values in that hash table and add them to the output array if they contain at least two elements

function listAnagrams (wordsArr) {

  const wordsTable = {};

  wordsArr.forEach(word =>  {
// in order to sort a string we must convert it into an array of its characters
    const wordKey = word.split('').sort().join('');
// if this sorted entry already exists push the word into the array with its sibling anagrams
    if (wordsTable[wordKey]) {
      wordsTable[wordKey].push(word);
    }
// or if we have not yet visited any anagrams of this word, create a new array for it
    else wordsTable[wordKey] = [word];
  });

  const output = [];

  Object.keys(wordsTable).forEach(wordKey =>  {
    const anagrams = wordsTable[wordKey];
// only include lists with more than one anagram
    if (anagrams.length > 1) {
      output.push(anagrams);
    }
  });
  return output;
}

"Minified" solution:

const anagramDetector = strArr => Object.values(
  strArr.reduce((hash, word) => {
    const wordSort = word.split('').sort().join('');
    if (hash[wordSort]) hash[wordSort].push(word)
    else hash[wordSort] = [word];
    return hash;
  }, {})).filter(anagrams => anagrams.length > 1)

Additional Resources

The REPLs:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment