How do you check whether two strings are anagrams of each other?
Two strings are anagrams when they have the same letters with the same counts. So you count the letters in one and take them away in the other.
def is_anagram(a, b):
if len(a) != len(b):
return False
counts = {}
for letter in a:
counts[letter] = counts.get(letter, 0) + 1
for letter in b:
if letter not in counts:
return False
counts[letter] = counts.get(letter, 0) - 1
return True
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
So how does it work? The first loop builds a count of every letter in the first string. The second loop takes one away for every letter in the second string. If a letter is not there at all, or if it runs out, then the strings are not anagrams.
And you check the lengths first, because two strings of different lengths can never be anagrams, and the check costs nothing.
So the complexity is O of n for the time, where n is the length of the strings, and O of k for the space, where k is the number of different letters.
The last question in this topic compares it with the one-line version.