Anagram Checker

I was recently tasked in a technical interview to implement a function that iterated through an array of strings and checked if each string was an anagram of a string before it, returning an alphabetically sorted array of the results. The caveat was that certain features such as reverse() were not allowed.

So given the array [‘drag’, ‘grad’, ‘’dad’, ‘banana’, ‘flimsy’, ‘add’] the function would output ['banana', 'dad', ‘drag’, ‘flimsy’]. I.e. Because 'grad' is an anagram of 'drag', it is removed from the array.

My first approach was to determine how to detect an anagram. Typically I would do the sort of word1.split('').sort() === word2.split('').sort, but that was not allowed. Instead, I implemented a function that first checked that the lengths of the two strings. Assuming they were of equal length, the function iterated through one of the strings, comparing it to the other, breaking if there is a letter that does not match up.

function isAnagram(word1, word2){
    if (word1.length !== word2.length) return false;
    word1 = word1.toLowerCase().split('')
    word2 = word2.toLowerCase().split('')
    for(let lttr of word1){
        // if letter in word1 is in word2, remove it from word2
        // if we never encounter a letter not in word2, 
        if (!word2.includes(lttr)){
            return false;
            break;
        } else {
            word2.splice(word2.indexOf(lttr), 1)
        }
    }
    return true
}

By splicing the word2 array, we ensure that the amount of letters is equal as well.

This function is a great start, but it is not going to work with the sample array we've been fed. Instead, I will call on this function inside of another one.

To begin, I wrote an if statement that examines the length of the array. We know that the the first string in the array will always be returned, because there is no string prior to it for it to be an anagram of. So if the array is empty or only includes only 1 string, the function will not continue and just return the array.

I chose to not modify the array in place and use the extra memory to create a solution array. By the logic explained above, we know that the first string will always be included in the solution, so the array is initialized with the first string in the array: let solution = [text[0]]. I then iterate over the subsequent array, calling on the isAnagram function to check if the subsequent strings are anagrams of any of the strings in the solution array. Note that the for loop starts with i = 1, not 0, because we have already checked text[0]. To do this, I filtered the solutions array against the current word in the for loop. If the word at text[i] is not an anagram, it is pushed into the solution array. (An alternate way of doing this would be to modify the array in place, checking isAnagram() only for words that have an index less than i.)

function arrayAnagramChecker(text) {
    if (text.length <= 1) return text;
    let solution = [text[0]]
    for(let i = 1; i < text.length; i++){
        if (!solution.filter(word => isAnagram(word, text[i])).length){
            solution.push(text[i])
        }
    }
}

This covers most of the work, but remember that the the results have to be returned in a sorted array, not in their original order. Again, normally I would just do a .sort or the slightly more laborious .sort((a, b) => a - b). This was not enabled so I to implemented a slightly more elaborate sort:

    solution.sort(function(a, b){
            if(a < b) { return -1; }
            if(a > b) { return 1; }
            return 0;
    })

Finally, our function:

function funWithAnagrams(text) {
    if (text.length <= 1) return text;
    let solution = [text[0]]
    for(let i = 1; i < text.length; i++){
        if (solution.filter(word => isAnagram(word, text[i])).length === 0){
            solution.push(text[i])
        }
    }
    solution.sort(function(a, b){
            if(a < b) { return -1; }
            if(a > b) { return 1; }
            return 0;
    })
    return solution
}

function isAnagram(word1, word2){
    if (word1.length !== word2.length) return false;
    word1 = word1.toLowerCase().split('')
    word2 = word2.toLowerCase().split('')
    for(let lttr of word1){
        // if letter in word1 is in word2, remove it from word2
        // if we never encounter a letter not in word2, 
        if (!word2.includes(lttr)){
            return false;
            break;
        } else {
            word2.splice(word2.indexOf(lttr), 1)
        }
    }
    return true
}

And, just for kicks, I rewrote the function in Python, although I utilized .sort there and also the .sorted() function in a lambda to avoid create a separate function.

def funWithAnagrams(text):
    if len(text) <= 1:
        return text
    solution = [text[0]]
    i = 1
    for i in range(len(text)):
        # if current word is not an anagram of list of solutions, add to solutions list
        anagrams = list(filter(lambda x : sorted(x) == sorted(text[i]), solution))
        if not anagrams:
            solution.append(text[i])
    solution.sort()
    return solution