Anagram Program in Python

Overview

This article will determine if two strings are Anagrams in Python. Anagrams are strings with the same character content, and the characters' frequency(or number) are also the same. So, let us discuss our Anagram program in Python.

What is the Anagram of a String?

An anagram of a string is another string that contains the same characters. However, the order of characters may or may be different. The below image shows anagram strings:

What is Anagram of a String

For example, save and vase are anagrams. Because save contains all the letters in vase, like 's','a', 'v', 'e', although the order of the letters may be different.

Other examples of anagrams are : state and taste, cat and act, peach and cheap, etc.

Anagram Program in Python

For the Anagram Program in Python, our problem statement may be something similar to the below-given problem statement:

Question:

We now have different approaches to solving Python's Anagram program. Let us discuss them one by one.

1. Using sorted() function

We must be familiar with Python's sorted() function. The sorted() function returns a sorted list, of any iterable(such as list, dictionary, tuple) passed to it. Strings are sorted alphabetically, and numbers are sorted numerically.

Now, our approach to solving this Anagram program in Python will be:

First, check whether the given strings have the same length(unequal length strings can never be anagrams)
Sort the given Strings
Compare if both the strings after sorting are the same.

Code:

Output:

Logic Explanation:

Firstly, we have compared the lengths of the string to verify if they are the same. If they are of unequal lengths, we return False and quit.
Then, we can sort the given strings a and b and store them into two variables, first and second.
Finally, we can compare first and second. If they are the same, we can return True. Otherwise, we will return False.

Time Complexity: $O(nLogn)$

Since we are using sorted() function, which in the worst case takes $O(nLogn)$ to sort, the time complexity becomes $O(nLogn)$ .

Space Complexity: $O(n)$

This space is used for sorting because sorted() in Python uses Timsort, which has a space complexity of $O(n)$

2. By Counting character

Our second approach to finding Anagram program in Python involves finding out the anagrams of a String by counting the number of characters in each string. We assume that there are at most 256 characters, and our input strings a and b will consist of lowercase English letters.

Code:

Output:

Logic Explanation:

Firstly, we will initialize two lists of length 256 with 0.
Also, we compare the lengths of the two strings for the same reasons we discussed above.
Then, we iterate over each of the strings s1 and s2. And while iterating through the string, we store the count of the ASCII value of each character. "ord" is used to find the ASCII values of the character. For example, for the string "cat", the following will be stored:

:::

Note: ASCII is a 7-bit character set containing 128 characters. It contains the numbers from 0-9, the upper and lower case English letters from A to Z, and some special characters used by modern computers.

After that, in our count_str1 and count_str2 we will store the count of the characters of each of the strings.
Finally, we will iterate over the strings and compare whether their number of characters are same or not. In any case, we get a different character count. We will break from the loop and return False. Otherwise, we will return True.

Improvement Over the Above Solution:

In the above solution, we use two lists to store our character counts for the strings. We can, however, use only one array and increment its index's count by one whenever we encounter a character in the first string, and decrement the count by 1, whenever we find the same character in another string.

Code:

Output:

Here, we increment the count by 1 for the first string and simultaneously decrement the count by 1 for the second string. Hence, if the same characters have the same count, our resultant list count_str will have all the indexes as 0 counts.

Time Complexity: $O(N)$

Since we iterate over the length 'n' strings to store their character count, our average and worst-case time complexity are $O(n)$ . If strings are of unequal lengths, the complexity becomes O(1) because only 1 comparison will be done.

Space Complexity: $O(N)$

The average and worst-case space complexity are O(N), where N is the strings' length. If strings are of unequal lengths, the complexity becomes O(1). :::

3. By Counter() function

Counter is a container included in the Python collections module. Counter() is a sub-class of dict in Python, where the elements and their respective count are stored as a dictionary. Counter calculates and stores the frequency of the element passed to it.

Example:

Output:

So, for obvious reasons, we can use collections. Counter to compute our result by calculating both lists' character count. They can help us to solve the Anagram program in Python.

Code:

Output:

Logic Explanation:

Counter counts the frequency of characters in str1 and str2.
We check whether the characters' frequency is the same. If they are the same, then we return True. Otherwise, we return False.

Time Complexity: $O(N)$

Time taken to construct a counter is $O(N)$ because the counter function has to iterate over the input, but operations on individual elements remain $O(1)$ . So, the overall time complexity is $O(N)$ .

Space Complexity: $O(1)$

We are not using any extra space in our code, and just the counters are counting the frequency of our strings and being compared. Hence, it will take a constant space of $O(1)$ .

4. Reverse Anagram check

Let us now write some code to check if the anagram of a string is palindrome or not.

Note: Palindrome strings are the strings that read the same backward or forward

The above strings are anagrams and palindromes. Now let us see the code for the same.

Code:

Output:

Logic Explanation:

We first check if the strings are anagrams by using our collections.Counter module.
Then, we check if the original string str1 and the string str2 when reversed, return the same result or not.
str[::-1] operation reverses our list or string. So, by using str[::-1], we reverse our second string and compare it with our first original string.

Time Complexity: $O(N)$

Our counter functions take time of $O(N)$ . And, reversing our string by str[::-1] operation also takes O(N) time for an input of length 'N'. So, the overall time complexity is $O(N)$ .

Space Complexity: $O(1)$

We are not using any extra space in our code, apart from some local variables, but just the counters are counting the frequency of our strings and been compared. Hence, it will take a constant space of $O(1)$ .

5. Using Position Verification Technique

In the Position Verification technique, a position level is compared to check anagrams. We can achieve this by verifying the first string's positional character with each positional character string in the other string. If the first string holds a similar match with the other string, it is declared an anagram.
However, this technique does not add to any improvement to time or space complexity, and adds complexity to our existing code. Hence, this technique is not recommended because of it's complexity and no significance added.
Let's check the code to solve the Anagram program in Python.

Code:

Output:

Conclusion

In this article, we discussed the Anagram program in Python. Let us recap once what we learned throughout:

Anagrams are strings with the same characters and count.
We can use sorting technique or use some count to find out anagrams of a string
We can also use the collections.counter() from the collections module to store the frequency of the characters of the string.
We also saw how we could check if two strings are anagrams and palindrome simultaneously.
Finally, we learned about the position verification technique of finding anagrams.