Anagram Test Algorithm

Anagrams! Everyone loves anagrams! Passing the time during COVID-19 quarantine has left me to my own devices, practicing coding algorithms seems to be the skill that needs the most work. This post addresses a couple of solutions for testing if one string is a anagram of another.

Character Map it Out

The first solution that made sense involved building a character map for each string to store the count of each character and then comparing the counts to determine if the strings are anagrams.

For example, the phrase "Green Eggs and Ham" produces the object

{ g: 3, r: 1, e: 3, n: 2, s: 1, a: 2, d: 1, h: 1, m: 1 }

The phrase "Harmed Gang Genes" produces a similar javascript object

{ h: 1, a: 2, r: 1, m: 1, e: 3, d: 1, g: 3, n: 2, s: 1 }

A quick examination reveals that both character maps contain the same number of characters, and each character occurs in both objects the same number of times. The anagram test should return true in this case.

Steps

1. Convert each string into a character map. Remove all non-word characters and convert them to lowercase.
2. Compare the number of keys (unique characters) of each map. If they're not equal, then the anagram test fails, so return false.
3. Verify that every character in the first map has the same number of characters in the second.

function anagrams(stringA, stringB) {
    // Place strings into a character map 
    // and compare count.
    const charMap = string => {
        const map = {}
        const arr = string
            .replace(/[^\w]|_/g, "")
            .toLowerCase()

        for (let char of arr) {
            map[char] = map[char] + 1 || 1
        }

        return map
    }
    // Convert each string into a character map.
    const mapA = charMap(stringA);
    const mapB = charMap(stringB);
    const mapAKeys = Object.keys(mapA)
    const mapBKeys = Object.keys(mapB)
    // Compare the number of keys
    if (mapAKeys.length === mapBKeys.length) {
        // Verify that first map matches second
        return mapAKeys.every(char => mapA[char] === mapB[char])
    }
    else
        return false
}

Just Flip it and Reverse it

While doing research on solving the anagram algorithm (because that's what I do in my spare time nowadays), was enlightened by a more clever solution.

It turns out that if you sort the letters alphabetically in the two strings, the resultant strings will be identical if the strings are anagrams.

The result of this method for "Green Eggs and Ham" would be "aadeeeggghmnnrs". Any string that would pass as an anagram would produce the same result.

Steps

1. Convert the original strings to sorted strings. Remove the non-word characters, convert to lowercase, convert to an array, sort, and convert back to a string.
2. Compare the two sorted strings.

function anagrams(stringA, stringB) {
    // Sort the strings and compare.
    const sortString = (string) =>
        string
            .replace(/[^\w]|_/g, '')
            .toLowerCase()
            .split('')
            .sort()
            .join('')
    return sortString(stringA) === sortString(stringB)
}

Taking advantage of the javascript sort method produces a more concise and readable solution. Thanks for the idea Stephen Grider.

Happy coding!

Cover photo by Amador Loureiro on Unsplash