sarath joseph sarath joseph - 1 month ago 6
Python Question

Checking for anagram strings in linear time

So given an input of two strings I have the following linear time solution to check if one string is an anagram of the other. I wanted a more concise and pythonic linear time solution to this.

def perm_check(str1,str2):

if len(str1)!=len(str2):
return False

d1,d2={},{}

for i in range(len(str1)):

l1=str1[i]
l2=str2[i]

if l1 in d1:
d1[l1]+=1
else:
d1[l1]=1


if l2 in d2:
d2[l2]+=1
else:
d2[l2]=1


for letter in d1:

if letter not in d2:
return False

if d1[letter] != d2[letter]:

return False

return True


print(perm_check("stab","bats"))


How can I optimize this?

Answer

You can use python collections.Counter class to do this. Basically, in anagrams, the count of each character has to be same between the two strings, so all you need is a character count of each character in both the strings, and compare them. The Counter class will create the dictionaries for you, which you can directly compare.

from collections import Counter

def is_anagram(string1, string2):
    return Counter(string1) == Counter(string2)

Result:

>>> is_anagram("helper", "perhel")
True
>>> is_anagram("helper", "perhe")
False
>>> is_anagram("helper", "perhes")
False