Skip to content
loading...

re: Learning Algorithms with JS, Python and Java 7: Anagrams VIEW POST

FULL DISCUSSION
 

Great article Tommy!

I love finding smaller solutions to problems, here is a similar attempt to your question on anagrams.

function anagrams(a, b) {
  a = a.replace(/[^\w]/g, "").toLowerCase();
  b = b.replace(/[^\w]/g, "").toLowerCase();

  if (a.length !== b.length) return false;

  return [...a].sort().join() ===  [...b].sort().join()
}

 

There's another clever solution using prime numbers which is O(n): You create a map of characters to prime numbers (just use the first 26 primes for simplicity), then store a "total" value and for each character in the string, multiply the total by the prime value of the character to get the "prime sum". Then check if the prime sum of the two words is equal.

Edit: Snippet to make the method clearer

const primes = new Map([['a', 2] /* etc */]);

function anagrams(wordA, wordB) {
    return primeSum(wordA) == primeSum(wordB);
}

function primeSum(word) {
    let total = 1:

    for (let char of word) {
        let value = primes.get(char.toLowerCase()):

        total *= value === undefined ? 1 : value;
    }

    return total;
}
 

This is a great solution Sam, the only thing I worry about is that multiplication though theoretically is an O(1) operation, but in for strings of size > 50, we will have resort to Big integers and multiplication there is not exactly O(1).

Also played a bit of code golf with your algorithm

const primeSum = word =>
  word
    .map(char => primes.get(char.toLowerCase()))
    .filter(char => char !== undefined)
    .reduce((prev, cur) => prev * cur);

A valid point - I didn't consider large strings that might cause an overflow. At that point a character map solution may become more efficient than using big arithmetic, though it would be interesting to test and see.

Nice golfed solution!

 

Nice thing about this method, you can use modulus to check if a string is a substring of another (“apple” to “applesauce”).

That might give false positive for jumbled words, for example paple would pass the modulous check.

code of conduct - report abuse