I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity (\$O(n)\$ where \$n\$ is the length of the given string(s)).
My approach for doing this is to essentially maintain a dictionary of the characters and their occurrences. For the first string, I increment the key corresponding to a character; for the second string, I decrement the key corresponding to the character. At the end, I check if every key in the dictionary has a value of 0: if so, the number of chars in the first string 'cancel out' those in the second, which means the occurrences are equal and the strings are anagrams. Else, the strings are not anagrams.
Does this function run in linear time? When I iterate through the strings to add to the dictionary, that's linear I think. But does checking every key in the dictionary afterwards take linear time as well? If so, this would be quadratic in its complexity. How would I resolve the issue then, since I think to make this function linear the dictionary must be used but in a smarter way.
def are_anagrams(s1,s2):
"""Returns True if s1 and s2 are anagrams of one another.
False otherwise.
Precondition: s1, s2 are both strings """
if len(s1) != len(s2): #automatic failure
return False
#same length
d = {}
index = 0
bound = len(s1)
while index < bound: #iterate through each string and its chars
s1_char = s1[index]
s2_char = s2[index]
#update d for s1
if s1_char not in d:
d[s1_char] = 1
elif s1_char in d:
d[s1_char] += 1
#update d for s2
if s2_char not in d:
d[s2_char] = -1
elif s2_char in d:
d[s2_char] -= 1
index += 1
for key in d:
if d[key]: #if d[key] != 0, one string has an additional/fewer
#character
return False
return True
from collections import Counter; def are_anagrams(str1, str2): return Counter(str1) == Counter(str2)
... \$\endgroup\$