Python: check if two strings are permutations of each other

Another question I cover in a presentation I’m preparing for “Open University meets Open Source” meetups.

What is a Permutation?

Permutation is the action of rearranging objects, characters or symbols into different, unique sequences.

Each sequence is called ‘permutation’.

It’s common to see people mix permutation with combination, but those are two different things. Remember, combination doesn’t care about the order, while permutation does.

Examples of permutations

ALL the permutations of {7, 8, 9} are (7, 8, 9), (7, 9, 8), (9, 7, 8), (9, 8, 7), (8, 9, 7) and (8, 7, 9).

A possible permutation of the ‘hello’ string, is ‘lloeh’.

How to tell if one string is a permutation of another string using Python?

We’ll explore several different solutions to the above question.

Collections Solution

import collections

def are_permutations(str1, str2): 
 """Returns True if the first given string is a permutation of the second 
 given string. 
 perm = collections.defaultdict(int) 
 for char in str1: 
 perm[char] += 1 
 for char in str2: 
 perm[char] -= 1 
 return not any(perm.itervalues())

The idea is to add key of each character in the first string to the dictionary and increase it by 1 for each appearance. Then, for the second string, decrease for each character’s appearance. In the last line, we return True only of all keys are equal to zero. If not, we return False.

This solution time complexity is O(n) since worst case is to go over each character of the strings.

We used collections (which I’ll go over in a minute) and ‘any’. For those who are not familiar with ‘any’, it’s a built-in function in Python that returns True if any element in the given iterable is True, if at least one is not, then it will return False.

Collections & defaultdict

You’ll note we are using the collections module in this solution. Collections is part of the Python standard library and it implements several specialized container datatypes, such as Deque, Counter and OrderedDict.

In our example, we used ‘deafultdict’. It’s a subclass of ‘dict’ class and its functionality is very similar to a regular dict, but there is one important difference between the two. If you’ll try to access non-existing key in a regular dict, you’ll receive a KeyError exception, in ‘collections.defaultdict’ however, it will create the item you are trying to access.

It does so by defining a new method called ‘__missing__’ and an instance variable called ‘default_factory’. Everything else is inherited from the ‘dict’ class.

For more information on collections and ‘defaultdict’ take a look here.

Sorting Solution

def are_permutations(str1, str2): 
 return (len(str1) == len(str2) and sorted(str1) == sorted(str2))

Much “cleaner” and probably more straightforward solution of comparing the length of both strings and compare them after sorting each string.

This solution is less effective. Its time complexity is O(n log(n)).

One thought on “Python: check if two strings are permutations of each other

  1. Just a quick note – mathematically, using a notation of {7, 8, 9} signifies that the order does not matter, so basically saying that {7, 9, 8} is a permutation of the above is irrelevant since they are both the same. Instead, use an ordered set (tuple) notation: (7, 9, 8) and (9, 8, 7) are indeed permutations of {7, 8, 9}.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s