A solution in Python which has a O(n+m) time complexity. It iterates through the first string and counts up the occurences of each character, and then does the same for the second string but decrements the count instead. If the two strings are anagrams then the count for every character should be 0.
Decided to handle all 128 ASCII codes so that the function works with all ASCII characters and not just capital letters, and it removes the need to subtract a base value from each of the ASCII values to convert it to a 0-based index.
def is_anagram(s1, s2): # can return 0 immediately if the strings are different lengths if len(s1) != len(s2): return 0 # for counting the ASCII characters 0 to 127 counts = *128 # increment the count for each character in the first string for c in s1: counts[ord(c)] += 1 # decrement the count for each character in the second string for c in s2: counts[ord(c)] -= 1 # the strings are anagrams if all the counts cancel each other out return 0 if any(counts) else 1
There is a simple optimisation to check that the strings are the same length at the start of the function; if the strings are different lengths then they cannot be anagrams. Would be significant improvement for very big strings.
A totally inconsequential optimisation (but why not) is the use of the any() function instead of sum(). It is ever so slightly faster as it only needs to do a comparison with 0 instead of addition, and it does lazy evaluation, meaning it will return as soon as a non-zero value is found.
%timeit sum(*128) 100000 loops, best of 3: 2.48 µs per loop %timeit any(*128) 100000 loops, best of 3: 2.07 µs per loop %timeit sum(*128) 100000 loops, best of 3: 2.47 µs per loop %timeit any(*128) 1000000 loops, best of 3: 764 ns per loop
Out of interest, I compared the runtime with a solution that use sorting to compare the strings (shown below). The time complexity for sorting is O(n log(n)), but for short strings the function below is faster. The point where the function above is faster is about strings of length 70 on my laptop.
def is_anagram(s1, s2): return 1 if len(s1) == len(s2) and sorted(s1) == sorted(s2) else 0