Python Program to Check if Two Strings are Anagram

Problem Description

Write a Python Program to check if the two strings are anagram.

What is Anagram?

An anagram in Python is a pair of strings that have the same characters, but in a different order. It involves rearranging the letters of one string to form the other.

Example: Consider the words “listen” and “silent“.
Both words contain the same characters (‘l’, ‘i’, ‘s’, ‘t’, ‘e’, ‘n’), but in different orders. By rearranging the letters of one word, we can form the other. This makes “listen” and “silent” an example of an anagram pair.

Problem Solution

There are several ways to check whether two strings are anagrams or not in Python. Let’s look at the different techniques in detail.

Method 1: Using sorted() Function

In this approach, we will check whether the two strings are anagrams or not using sorted() function.

Program/Source Code

Here is source code of the Python Program to detect if two strings are anagrams using sorted() function. The program output is also shown below.

```s1=raw_input("Enter first string:")
s2=raw_input("Enter second string:")
if(sorted(s1)==sorted(s2)):
print("The strings are anagrams.")
else:
print("The strings aren't anagrams.")```
Program Explanation

1. User must enter both the strings and store them in separate variables.
2. The characters of both the strings are sorted into separate lists.
3. They are then checked whether they are equal or not using an if statement.
4. If they are equal, they are anagrams as the characters are simply jumbled in anagrams.
5. If they aren’t equal, the strings aren’t anagrams.
6. The final result is printed.

Time Complexity: O(n log n)
The time complexity of the code is O(n log n), where n is the length of the longer string.

Space Complexity: O(n)
The space complexity is O(n), where n is the length of the longer string, due to the sorted() function.

Note: Join free Sanfoundry classes at Telegram or Youtube
Runtime Test Cases

Testcase 1: The runtime output of the Python program to check whether two strings are anagrams is shown below, where the first string is “listen” and second string is “silent”.

```Enter first string:listen
Enter second string:silent
The strings are anagrams.```

Testcase 2: The runtime output of the Python program to check whether two strings are anagrams is shown below, where the first string is “hello” and second string is “world”.

```Enter first string:hello
Enter second string:world
The strings aren't anagrams.```

Method 2: Using Counter() Function

In this approach, we will check whether the two strings are anagrams or not using counter() function.

Program/Source Code

Here is source code of the Python Program to detect if two strings are anagrams using counter() function. The program output is also shown below.

```from collections import Counter

def is_anagram(str1, str2):
# Create Counter objects for both strings
counter1 = Counter(str1)
counter2 = Counter(str2)

# Compare the counters
return counter1 == counter2

# Test the function
string1 = input("Enter the first string: ")
string2 = input("Enter the second string: ")

if is_anagram(string1, string2):
print("The strings are anagrams.")
else:
print("The strings are not anagrams.")```
Program Explanation

1. In this program, the is_anagram function takes two strings, str1 and str2, as input.
2. It creates Counter objects, counter1 and counter2, for both strings.
3. The Counter function counts the occurrence of each character in the string.
4. Then, the function compares the counters using the == operator and returns True if they are equal, indicating that the strings are anagrams. Otherwise, it returns False.

Time Complexity: O(n)
The time complexity of the code is O(n), where n is the length of the longer string. This is because the Counter function iterates over the strings once to count the occurrence of each character.

Space Complexity: O(n)
The space complexity is also O(n), as the Counter objects store the character counts for both strings.

Runtime Test Cases

Testcase 1: The runtime output of the Python program to check whether two strings are anagrams is shown below, where the first string is “study” and second string is “dusty”.

```Enter the first string: study
Enter the second string: dusty
The strings are anagrams.```

Testcase 2: The runtime output of the Python program to check whether two strings are anagrams is shown below, where the first string is “tall” and second string is “all”.

```Enter the first string: tall
Enter the second string: all
The strings are not anagrams.```

Method 3: Using Recursion

In this approach, we will recursively check whether the two strings are anagrams or not.

Program/Source Code

Here is source code of the Python Program to check if two strings are anagrams using recursion. The program output is also shown below.

```def is_anagram(str1, str2):
if len(str1) != len(str2):
return False

if len(str1) == 1:
return str1 == str2

for i in range(len(str1)):
if str1[i] in str2:
remaining_chars = str2[:str2.index(str1[i])] + str2[str2.index(str1[i]) + 1:]
if is_anagram(str1[:i] + str1[i+1:], remaining_chars):
return True

return False

# Test the function
string1 = input("Enter the first string: ")
string2 = input("Enter the second string: ")

if is_anagram(string1, string2):
print("The strings are anagrams.")
else:
print("The strings are not anagrams.")```
Program Explanation

1. In this program, the is_anagram function takes two strings, str1 and str2, as input.
2. It first checks the base cases: if the lengths of the strings are not equal or if the length is 1, it compares the strings directly.
3. For the recursive case, it iterates through each character in str1 and checks if it is present in str2. If a match is found, it removes the character from both strings and recursively checks if the remaining characters can form an anagram.
4. If any recursive call returns True, the function returns True. If no match is found or no recursive call returns True, the function returns False.

Time Complexity: O(n!)
The time complexity of the code is O(n!), where n is the length of the longer string.

Space Complexity: O(n)
The space complexity is O(n), where n is the length of the longer string, due to the recursive function calls and additional space used for the remaining characters.

Program Output:

The runtime output of the Python program to check whether two strings are anagrams is shown below, where the first string is “teacher” and second string is “hectare”.

```Enter the first string: teacher
Enter the second string: hectare
The strings are anagrams.```

To practice programs on every topic in Python, please visit “Programming Examples in Python”.

If you find any mistake above, kindly email to [email protected]