[Challenge] Anagram Detector

#Code Challenge, April 26th 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview, similar to the FizzBuzz Challenge often used at places like Facebook and Google.

For this week’s challenge, inspired by a question reported to have been asked in developer job interviews at Microsoft:

Write a function in your favorite programming language that will accept any two strings as parameters and return “1” if they are anagrams and “0” if they are not.

For simplicity’s sake, focus only on strings composed from uppercase letters (in hex ASCII - from 41 (A) to 5A (Z)) and space characters.

####Scroll down and reply to this thread with your code to participate! Don’t just submit your code, remember to explain your solution, too! Please link to your code on a site like repl.it to make assessing your entry easier (see below).


##Extra Credit
####Intermediate Difficulty
If you’d like to go a step further:

Make sure that your answer has no more than O(n + m) time complexity, where n is the length of the first string and m of the second.

Make your submission as efficient as possible! You can presume that the hypothetical interviewer in this case is looking for the most direct approach that does not involve len(n)! permutations.

Learn more about Big O notation and time complexity here and here. There’s also an old (and thus unsupported) Codecademy course on Big O, if you prefer.

##The Winners

For the “best entries,” see here!

Though it is now too late for any more submissions to be considered as a “best entry,” we encourage you to submit further responses anyway! It is our hope not only that you’ll benefit from the experience in testing your skills or preparing for interviews, and your posting your answer here will build up a library of content that will help others to learn too.


###How to participate

  • Use any language taught on Codecademy (Python, Java, Ruby, JavaScript, PHP, etc.)

  • Please include a link to your code running on service like repl.it, CodePen, JSFiddle, or our very own CodeBits so that your fellow students can learn from your submission easier and faster - if we have hundreds of submissions, we may not have time to assess entries that do not have links in this manner

  • If you want to post your code directly, please make sure that it is correctly formatted!

Happy coding!


The fine print:

  • Remember, the point of code challenges like these is to test and stretch yourself with an unusual problem, so don’t be dissuaded if you find it difficult or don’t know where to start! Start with Googling, but see if you can find out how to think about the problem and what tools you need to solve it, but don’t just go looking for the solution itself. This way, it’ll be a better learning exercise for you - developers can’t always find and copy “the right answer” online, which is why questions like these are used in developer job interviews! Interviewers want to be able to see how you think through problems and not just whether or not you can solve them.
  • If you are interested in “winning” the code challenge, please don’t use any unusual repos or anything that will make it difficult for us or your fellow users to assess your answer quickly.
  • Do you have a code challenge to share with other users? Issue it! Make a new topic with [Challenge] in the title to open a challenge, maybe we’ll even feature it in our next newsletter!

Hi code community, I’m Roy, a moderator here on the forums. Here’s a sample solution I made last night while we were discussing this challenge. I look forward to seeing your responses too!

https://repl.it/H0vl/6

The logic if fairly straight forward, and explained in the comments.

The verbose version is appended for testing, only.

Raw code

def is_anagram(a, b):
  # are they strings?
  if type(a) != str or type(b) != str: raise TypeError
  a = a.replace(' ', '')
  b = b.replace(' ', '')
  # do the lengths match when spaces are removed?
  if len(a) != len(b): return 0
  # are the characters in alpha ASCII range?
  if a.isalpha() and b.isalpha():
    base_wp = sorted(list(a.upper()))
    test_wp = sorted(list(b.upper()))
    while base_wp:
      # do the data points match?
      if base_wp.pop() != test_wp.pop(): return 0
    return 1
  raise ValueError

Usage

is_anagram('JIM MORRISON', 'MR MOJO RISIN')
4 Likes

Solution in PHP

function anagram($first, $second){
	$first_length = strlen($first);
	$second_length = strlen($second);
	$flag = 0;
	if($first_length == $second_length){
		$first_array = str_split($first);
		$second_array = str_split($second);
		for($i=0; $i<$first_length; $i++){
			if($first_array[$i] != $second_array[$second_length - $i - 1]){
				$flag = 1;
				break;
			}
		}
	}
	else{
		$flag = 1;
	}

	print_r(($flag == 0) ? 'Anagram' . PHP_EOL : 'Not an Anagram' . PHP_EOL);
}

anagram($argv[1], $argv[2]);

Updated Solution in PHP to find any rearranged anagrams

function anagram($first, $second){
	$first_length = strlen($first);
	$second_length = strlen($second);
	$flag = 0;
	if($first_length == $second_length){
		$first_array = str_split($first);
		$second_array = str_split($second);
		sort($first_array);
		sort($second_array);
		for($i=0; $i<$first_length; $i++){
			if($first_array[$i] != $second_array[$i]){
				$flag = 1;
				break;
			}
		}
	}
	else{
		$flag = 1;
	}

	print_r(($flag == 0) ? 'Anagram' . PHP_EOL : 'Not an Anagram' . PHP_EOL);
}

anagram($argv[1], $argv[2]);

1 Like

https://repl.it/H2JZ/2

Raw Code:

def anagramChecker(word1, word2):

  stripWord1 = word1.replace(' ', '')
  stripWord2 = word2.replace(' ', '')

  sortWord1 = sorted(stripWord1)
  sortWord2 = sorted(stripWord2)

  if (sortWord1 == sortWord2):
    return 1
  else:
    return 0
    
print(anagramChecker('ALEC    GUINNESS', 'GENUINE CLASS'))
print((anagramChecker('PANAMA', 'BANANA')))

Simple solution using Python. I’m assuming the inputs will be strings with only upper case letters and spaces, so all that is needed is to strip out the spaces and compare the sorted lists of characters, which should be identical strings for anagrams.

4 Likes
//Only a beginner. I know I should check for strings, strip out whitespace and punctuation, clean up the submitted data, but for simplicity's sake I'm going to pretend the person submitting is nice. Won't get me a job but it's made me smile.

function anagrammer (str1, str2) {
  
  var tidyStr1 = str1.split('').sort().join('');
  var tidyStr2 = str2.split('').sort().join('');

//array it, sort it, smush it back
  
  if (tidyStr1 === tidyStr2) {
    return "anagram";
  } else {
    return "not an anagram";
  }
  }

console.log(anagrammer("lampost", "cotton"));
console.log(anagrammer("angel", "angle"));
2 Likes

Your answer only fits when two words have their letters inversed but not rearranged.
See https://en.wikipedia.org/wiki/Anagram

1 Like

Rails, O(n+m)

def char_frequencies(phrase)
  frequencies = {}
  phrase.split("").each do |char|
    if frequencies.key?(char)
      frequencies[char] += 1
    else
      frequencies[char] = 0
    end
  end
  frequencies
end

def anagrams?(phrase1,  phrase2)
  char_frequencies(phrase1.downcase) == char_frequencies(phrase2.downcase)
end

def anagrams(phrase1, phrase2)
  anagrams?(phrase1, phrase2) ? 1 : 0
end

Make the comparison case-insensitive by downcasing both phrases.
Use a hash map to track the frequency of each character in each phrase.
Ruby typically returns booleans from functions ending with '?'s, but we’ll add another function that returns a 1 or 0 to meet the spec.
If both phrases have the same characters with the same frequencies, they’re anagrams of each other.
Checking the equality of the two hashes fits our O(n+m) time constraint because it only needs to check all the keys in the hashes, and there are only as many keys as there are characters.

2 Likes
// Splitting the strings into character arrays, sorting the arrays, and comparing them.
function stringsAreAnagrams($string1, $string2)
{
    $stringArray1 = str_split($string1);
    $stringArray2 = str_split($string2);
    
    sort($stringArray1);
    sort($stringArray2);
    
    return $stringArray1 === $stringArray2;
}

$string1 = 'anagram';
$string2 = 'granama';
echo stringsAreAnagrams($string1, $string2);
1 Like

First I checked if the two Strings have the same length, then I try a for loop checking that the i character equals the len-i-1 character.
If there is a character or length mismatch the loop terminates returning false.

And this is my function in Java:

public static boolean isAnagram (String s1, String s2){
        boolean state=(s1.length()==s2.length());
        int len=s1.length();
        for (int i=0; i<len; i++){
            if (state){
                state= (state && (s1.charAt(i)==s2.charAt(len-i-1)));
            }
            else break;
        }
        return state;
    }
1 Like

Solution in Javascript (certainly not the more efficient but it’s working):

https://repl.it/H2ou/1

Don’t know about the complexity of this :joy:

Here is my solution in python. I hope it covers intermediate problem as well.

def isAnagram(s1,s2):
	# init dictionary for storing chars and their counts (has O(1) for set and get)
	myMap = {}

	# count of distinct characters
	chars = 0

	# going through string 1 (s1)
	for ch in s1:
		if ch not in myMap:
			# if current char is not in dict, add it with value 1 and inc. chars value by 1
			myMap[ch] = 1
			chars += 1
		else:
			# if current char is in dict, add 1 to its number of occurences
			myMap[ch] += 1
	
	# going through string 2 (s2)
	for ch in s2:
		if ch not in myMap:
			# if current char is not in dict (from string 1), char is new and therefore return 0
			return 0
		else:
			# if char is in dict, substract 1 from its number of occurences
			myMap[ch] -= 1

		if myMap[ch] == 0:
			# if number of occurences in the current string is for the char the same as in the s1, substruct 1 from number of expected chars
			chars -= 1

		if myMap[ch] < 0:
			# in case of number of occurences of the char in s2 is greater then s1 return 0
			return 0

	if chars == 0:
		# if all chars has been used in both strings equaly return 1
		return 1
	else:
		# some chars has not been used in s2, so return 0
		return 0

UPDATE 1: Added comments to the code

Improved PHP solution stripping spaces and using a lambda for dryer code.

function stringsAreAnagrams($string1, $string2)
{
    $stringToSortedArray = function ($string) {
        $stringArray = str_split(str_replace(' ', '', $string));
        sort($stringArray);
        
        return $stringArray;
    };
    
    return $stringToSortedArray($string1) === $stringToSortedArray($string2);
}

https://repl.it/H2jv/0

Hi, here is my solution in JavaScript.

I’m sorry if my english is malformed somewhere, but it is not my native language.

This works by looping one time through both strings. Inside this loop I collect the number of occurrences of each character on each string. I collect these counts in two arrays, one for each string. In these arrays the indexes correspond to the char codes, and the values correspond to the counts.

After the loop I compare the two arrays and if they have the same count for the same characters, the strings are anagrams.

I’m assuming the strings will only contain uppercase letters and spaces.

function isAnagram (string1, string2) {
    // These arrays will collect the counts.
    var arr1 = [], arr2 = [];
    var i = 0;
    // One loop to traverse both strings.
    // This loop will run n times, where n is the length of the longest string.
    while (i < string1.length || i < string2.length) {
        // It could happen that 'i' increases beyond the length of one of the two strings so first I check if there is a character at this index in the strings, and if this character is not a space. If it is a space it will just jump this character.
        if (string1.charAt(i) != '' && string1.charAt(i) != ' ') {
            // Then I increase the count for this character in the corresponding array.
            // The first time a character occurs I asign 1, the next times I increase 1.
            if (arr1[string1.charCodeAt(i)]) {
              	arr1[string1.charCodeAt(i)] += 1;
            }
            else {
              	arr1[string1.charCodeAt(i)] = 1;
            }
        }
        // Do the same for the other string.
        if (string2.charAt(i) != '' && string2.charAt(i) != ' ') {
            if (arr2[string2.charCodeAt(i)]) {
              	arr2[string2.charCodeAt(i)] += 1;
            }
            else {
              	arr2[string2.charCodeAt(i)] = 1;
            }
        }
        // Increase 'i'
        i++;
    }
    // After the loop I compare the two arrays, and if they have the same counts for the same characters, the strings are anagrams.
    i = ('A').charCodeAt(0); // Get the char code of the character 'A'
    while (arr1[i] === arr2[i] && i <= ('Z').charCodeAt(0)) {
     	  i++;
    }
    // After the loop if 'i' has increased beyond the char code of 'Z', all the counts were equal.
    return (i > ('Z').charCodeAt(0) ? '1' : '0')
}

https://jsfiddle.net/dwrdem7d/12/
https://repl.it/H2mo/4

1 Like

##Hey all,
Just a reminder to please try and include a link to the code you submit in https://repl.it/, if possible, for easier testing - this will help us test the solutions you propose and choose the best solution out of those that work.

You may still paste in raw, markdown-formatted code in your post, but we ask that you try and give us a link to your code in repl.it for ease of testing and evaluation also.

Happy coding!
~CC mods

Here’s my entry, using pure Javascript. My thinking is that each word or phrase is really just a set of letters, and two anagrams have matching sets of letters. My function arranges the letters so they can be compared, and then sees if they are a match.

var is_anagram = function(str1,str2){
   str1 = str1.replace(/\s/g,'').toUpperCase().split('').sort().join('');
   str2 = str2.replace(/\s/g,'').toUpperCase().split('').sort().join('');
   if (str1 === str2){
   //It is an anagram!  Return 1
   return "1";
   }else{
   //It's not a match.
   return "0";
   };
};

On each string:

  1. remove whitespace with regex
  2. convert to uppercase
  3. split into an array to make it possible to sort
  4. sort the array (alphabetically)
  5. convert back to a string (because it’s harder to compare arrays without looping)
    After this process, strings that are anagrams should produce the same string. If the produced strings don’t match, then you don’t have an anagram.

My working example is here: https://jsfiddle.net/clintongalloway/cfb0Lhxc/
I just saw that you prefer this so I took a few seconds to upload this https://repl.it/H2oZ/1

1 Like

Hi everyone,

Here I present you my Python code for solving the challenge so you can read it and test it yourselves. Right after it you will find a brief explanation on how the code works and how I came up with it:

https://repl.it/H2tf/4

So, if you have looked at the code you would have noticed that the most substantial part is contained in the anagrams function, which contains the logic that can tell if two strings are anagrams in O(n+m).

In order to be able to comply the time complexity constraint I assumed that both input arguments satisfied the precondition of being strings composed of uppercase ASCII letters. Then, if I wanted to accomplish the time complexity goal, I knew that I needed to iterate each argument one time at most. So, I came up with this idea of iterate over the first string and count the occurrences of each letter, and then iterate over the second string while trying to “undo” the counting I did before. This way, if the strings were actually anagrams, all my letters counts would be zero by the time I had finished iterating over the second string, and I wouldn’t have found any letter apart from the ones I encountered in the first string.

So, if we inspect the code of the anagrams function you will see that basically I use a dictionary for counting the letters occurrences. The first for loop is where I define each letter from the first word as a key in the dictionary, and I increment its value as I see them along the string:

for letter in first_string:
        letters_count[letter] = letters_count.get(letter, 0) + 1

Later on, in the second for loop, I walk through each letter of the second string and I retrieve from the dictionary its number of occurrences:

    for letter in second_string:
        occurrences = letters_count.get(letter, None)

If that value is higher than 1, then I decrease it and store it back, as I already managed to match a pair of the same letter in both strings:

if occurrences > 1:
            letters_count[letter] -= 1

Otherwise, if that value is exactly 1, that means I have just matched the last occurrence of that letter in the first string. Hence, I remove the letter from the dictionary as I shouldn’t be expecting to encounter this letter again while I finish my second string iteration.

if occurrences == 1:
            letters_count.pop(letter, None)

Lastly, if that value is None, it means that I have found a letter that I cannot match to an occurrence of the same letter in the first string. Therefore, I can immediately conclude that the strings are note anagrams and return False:

        if occurrences is None:
            return False

By the end of the loop, if no keys are left in the dictionary (meaning that I was able to match each letter from the second string with a letter from the first string and no letter from the first string remained without match), then the words are anagrams. Otherwise, they are not.

return True if not letters_count else False

On top of that, I defined a validate_string function that runs some checks to the guarantee those assumptions I made for the anagram function inputs, and it raises some custom made exceptions in case one of those checks fails.

Then I assembled both of the previous mentioned functions inside a wrapper function called anagram_detector, which also is responsible for translating the boolean value returned by anagram into a 1 or 0 accordingly.

Finally, I added some tests cases and an interactive routine that allows the user to run the whole test suite or just type in a pair of strings for detecting if they are anagrams.

Well, that is all about the code. I hope you liked it or you find it useful.
Thanks for reading it :slight_smile:


Carlos.

4 Likes

A post was split to a new topic: Read those docs

A post was split to a new topic: Exception handling

function isAnagram(word1, word2){
   var word2Arr = word2.split("");
   for(var letter of word1){
        var index = word2Arr.indexOf(letter);
        if(index == -1){
            return "0";
        }
        word2Arr.splice(index,1);
   }

   if(word2Arr.length == 0){
       return "1";
   }else{
       return "0";
   }
}

The function isAnagram takes two arguments: word1 and word2.
Then word2 gets spilled into an array of charactes called word2Arr. Then word1 gets looped through. Each letter gets queried in the word2Arr array. If a match is found, that letter gets removed from the word2Arr array. If a match is NOT found, it means word1 contains a letter that word2 does not, and is thus not an anagram of word2, and returns “0”. Once the loop has finished, the length of word2Arr is checked. If all the characters have been removed (an empty array), it means the word is an anagram and “1” is returned.

My solution in Java

import java.util.Arrays;
class Input{
    static int find(String x, String y){
        String s1=x.replaceAll("\\s","");
        String s2=y.replaceAll("\\s","");
        boolean state=true;
        if(s1.length()!=s2.length()){
            state=false;
        }else{
            char[] s1Array=s1.toCharArray();
            char[] s2Array=s2.toCharArray();
            Arrays.sort(s1Array);
            Arrays.sort(s2Array);
            state=Arrays.equals(s1Array,s2Array);
        }
        if(state){
            System.out.print("Anagrams");
            return 1;
        }else{
            System.out.print("Not anagrams");
            return 0;
        }
    }
}
class Anagram{
   public static void main(String...s){
       Input.find("TOM MARVOLO RIDDLE","I AM LORD VOLDEMORT");
   }
}

Following steps are involved in the code:

  1. Remove the white spaces using Regex
  2. Convert the Strings into character arrays
  3. Sort the characters in the array
  4. Use the equals() method to check for matches
  5. Return “1” if they are anagrams and “0” if they are not anagrams
1 Like