Arie Bregman

Linux And Stuff

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

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

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)).

1 Comment

  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

Your email address will not be published.

*

© 2017 Arie Bregman

Theme by Anders NorenUp ↑