Two ways to solve the Anagram problem using Python

Anagram - anagram

You can see above: the banner of the article is a GIF showing the phrases "supersonic" and "percussion". These two words share the same set of letters and can be rearranged to form a new word. Words like this are called " anagrams ". So what exactly is an anagram? According to Wikipedia, an anagram is a word or phrase formed by rearranging another word or phrase. Examples of anagrams are: "New York Times" ⇒ "monkeys write" or "evil" ⇒ "vile".

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase

" Determine whether two words are anagrams of each other " is a simple but classic puzzle in Computer Science and is often used as an "opening" question when interviewing candidates.

In this blog post, I will give typical solutions to this problem using Python language.

Topic

Write a program that takes a list of words and returns lists of sublists containing anagrams of each other.

Input:

["yo", "act", "flop", "tac", "foo", "cat", "oy", "olfp"]

Desired output:

There are many ways to solve this problem, but in this blog post I will only give 2 typical and quite optimal ways in terms of space and time complexity.

Approach 1: sort string

Anagram words use the same set of letters and have different sorting orders, so when we sort a pair of anagram strings in Python, the results will be the same.

So this approach will group anagram words together using its sorted string as key. My solution is as follows:

Input:

Output:

Space and time complexity analysis

Note: where w is the number of input words, n is the length of the largest word.

Space complexity is O(wn): since the space complexity of each word is O(n). Therefore, the space complexity of w words is O(wn).

Time complexity is O(w * nlogn):

1. Time complexity of iterating through list of words is O(w).
2. Time complexity of each string sort is O(n * logn).
3. Time complexity of appending a new element to the list is O(1).

Hence the time complexity of the solution is O(w * n * logn).

Approach 2: use prime numbers to check anagrams

Prime numbers have a fundamental property called unique factorization. This property states that every number greater than 1 can be written as the product of one or more prime numbers and that product is unique.

This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ

We will use this property to group words that are anagrams of each other. The approach is to assign 26 letters to any 26 prime numbers. Then we iterate through each word and calculate the product of the prime numbers corresponding to the letters in the word. Words with the same product are anagrams of each other according to the unique factorization property above. For example:

Note: from Python 3.8, math.prod is newly added

My solution for this approach is:

Input:

["cinema", "a", "flop", "iceman", "meacyne", "lofp", "olfp"]

Output:

Space and time complexity analysis

Note: where w is the number of input words, n is the length of the largest word

Space complexity is the same as above, which is: O(wn).
Time complexity is O(wn). Explanation:

1. Time complexity when iterating through a list of words once is O(w)
2. The time complexity to perform n multiplications (corresponding to n characters of a word) is O(n) (Assume that multiplication is O(1)).

Therefore time complexity is O(w * n)

Conclude

The above two solutions are not all the ways to check and group anagrams, but I hope this blog post can help you in some way. If you find the blog post interesting, please share it so that more people know about it. And look forward to more of my blog posts on the topic of Data Structure & Algorithm on TipsMake's Tech blog!

Kareem Winters

Update 12 February 2025