Two Ways to Solve the Anagram Problem Using Python

Two Ways to Solve the Anagram Problem Using Python is easier to approach with a clear overview and reliable steps. This guide organizes the essential information, highlights practical details, and explains what to check along the way.

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:

You will find 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):

• Time complexity of iterating through list of words is O(w).
• Time complexity of each string sort is O(n * logn).
• 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 instance:

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:

• Time complexity when iterating through a list of words once is O(w).
• 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. Please share it so that more people know about it if you find the blog post interesting. And look forward to more of my blog posts on the topic of Data Structure & Algorithm on this guide's Tech blog!

Final Thoughts

The most reliable way to handle two ways to solve the anagram problem using python is to follow the process in order, verify each important setting, and test the result before moving on. Use the guidance above as a practical reference, then adjust the details for your device, software version, or specific goal.