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 and put them into an array. i.e.:

kmno kmno bbc bbc dell dell

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

Any help will be greatly appreciated.

Solution 1

Javascript objects are excellent for this purpose, since they are essentially key/value stores:

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

// The output object
var anagrams = {};

for (var i in words) {
    var word = words[i];

    // sort the word like you've already described
    var sorted = sortWord(word);

    // If the key already exists, we just push
    // the new word on the the array
    if (anagrams[sorted] != null) {
        anagrams[sorted].push(word);
    } 
    // Otherwise we create an array with the word
    // and insert it into the object
    else {
        anagrams[sorted] = [ word ];
    }
}

// Output result
for (var sorted in anagrams) {
    var words = anagrams[sorted];
    var sep = ",";
    var out = "";
    for (var n in words) {
        out += sep + words[n];
        sep = "";
    }
    document.writeln(sorted + ": " + out + "<br />");
}

Solution 2

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.

Solution 3

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

Solution 4

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.

Solution 5

Probably not the most efficient way, but a clear way around using es6

function sortStrChars(str) {
  if (!str) {
    return;
  }
  str = str.split('');
  str = str.sort();
  str = str.join('');
  return str;
}

const words = ["dell", "ledl", "abc", "cba", 'boo'];

function getGroupedAnagrams(words) {
  const anagrams = {}; // {abc:[abc,cba], dell:[dell, ledl]}
  words.forEach((word) => {
    const sortedWord = sortStrChars(word);
    if (anagrams[sortedWord]) {
      return anagrams[sortedWord].push(word);
    }
    anagrams[sortedWord] = [word];
  });
  return anagrams;
}

const groupedAnagrams = getGroupedAnagrams(words);
for (const sortedWord in groupedAnagrams) {
  console.log(groupedAnagrams[sortedWord].toString());
}

View more solutions

Comments

[jiaoziren]

Could you please elaborate your code? I am even more confused after reading this. Thanks in advance.

[tomdemuyt]

Sure, text normalization is the process of transforming text into a single canonical form. The canonical form here is the text with its characters sorted.

[ravi]

Its case sensitive

[Lurifaxel]

Great solution! This is faster than solutions based on sorting. This is of time complexity O(n), compared to sorting that should be at best O(n logn), if I'm not mistaken. :) They might be easier to read though...

[Ronak07]

Thanks @Lurifaxel

[Simas Joneliunas]

please consider adding a comment explaining how your answer solves the OP's problem

[user992731]

Works great! Can you explain the logic a bit.

[Justin Thomas]

Shouldn't charMap.set(current, -1); be charMap.set(current,charMap.get(current) - 1);?

[marcobiedermann]

@JustinThomas good point but actually it is not needed. The reason for that is that the conditions checks if both strings have the same length. Still thanks for pointing that out!

[Justin Thomas]

What if you have: catt and caat?

[marcobiedermann]

You are right. I will adjust my code. Thanks for pointing out! +1

[Federico Baù]

Welcome to StackOverflow. While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please edit your answer to add explanations and give an indication of what limitations and assumptions apply.

[jithil]

high complexity.

[Luke_]

Please add an explanation to what this code does and how

[Banana]

Please explain what your code does. An explanation will help both current and future visitors understand your code.

[Vladi4]

Hi @FriendlyBanana, it solves the problem from the question. There is nothing to explain.

[gwar9]

This is cleaner than the second solution. It uses a frequency pattern by creating a object to keep track of the characters and uses non nested loops that maintain O(n) time.

[niio]

this line is not necessary I guess: result[char] = -1;

[code]

.join() without an argument will automatically join by commas, which probably isn't the best take. It's good practice to specify an empty string: .join("").

[GarfieldKlon]

Same for replace(), you should provide a replacement, in this case an empty string. Otherwise it will replace matches with undefined.