1.3 Given two strings, write a method to decide if one is a permutation of the other
This is a super idiomatic and easy to understand approach. Python strings are immutable, so we can’t avoid the new string allocations caused by sorting. The runtime is O(nlogn).
def are_permutations(string_one, string_two): return sorted(string_one) == sorted(string_two)
Counting with a dictionary counter
Instead of using sorted inputs, we compare the occurrences of each character from both strings. Will this use more space?
I think it depends. Lets assume a unicode character set.
If we’re dealing with inputs that are mostly unique, likely take up more space compared to inputs with lots of duplication because we’ll have more keys and count values. There’s also the overhead of the hashmap itself.
def are_permutations(string_one, string_two): from collections import Counter return Counter(string_one) == Counter(string_two)
Counting with a list
If we assume ASCII input, we can get away with a counter with a smaller memory footprint than a hashmap: an array!
def are_permutations(string_one, string_two): list_counter =  * 256 for s in string_one: idx = ord(s) list_counter[idx] += 1 for s in string_two: idx = ord(s) list_counter[idx] -= 1 if list_counter[idx] < 0: return False return True