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:
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:
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
if occurrences is None:
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