Check if two strings are anagrams in Python
In this Tutorial we will write a Python program to check if two string are anagrams are not.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase.
Problem Statement
Given two strings source and target, write a Python function to check whether the given strings are anagrams of each other or not.
If both are anagrams return true else false.
Examples of Anagrams are
//Example 1
Input: source = "anagram", target = "nagaram"
Output: true
// Example 2
Input: source = "below", target = "elbow"
Output: true
// Example 3
Input: source = "study", target = "dusty"
Output: true
// Example 4
Input: source = "night", target = "thing"
Output: true
// Example 5
Input: source = "act", target = "cat"
Output: true
Approach 1: Using Sorting
The simple way to check if strings are anagrams or not is too sort the both strings and compare them.
If they are equal then both are anagrams otherwise they are not.
We can use Python sorted() function to sort the strings.
sorted() is a built in function in Python, which returns the sorted string without modifying the existing string.
def CheckIfStringsAreAnagram(source: str, target: str) -> bool:
## Basic use case check if both strings length
if(len(source)!=len(target)):
return False
return sorted(s)==sorted(t)
Complexity
Time Complexity:
As we are using sorted() function, the worst case it takes O(nlogn).
So the Time complexity is O(nlogn).
Where n is the length of the string.
Space Complexity:
The space complexity is O(n).
Approach 2: Using Character Frequency Counter
We can check if both strings are anagrams or not without sorting the strings.
As both strings contains only alphabets, we can count the occurrences of each character in two strings and then compare the count.
Algorithm
- Check if both strings length equal or not.
- Create two counter arrays for both strings, as they contain only alphabets we can create arrays with size
26. - Then count the occurrences of each letter and store them in corresponding arrays.
- Finally compare both arrays count. If both arrays counts are equal then strings are anagram return
trueelse returnfalse.
def CheckIfStringsAreAnagram(source: str, target: str) -> bool:
if len(source) != len(target):
return False
numberOfAlphabets = 26
sourceCharacterCounter = [0]*numberOfAlphabets
targetCharacterCounter = [0]*numberOfAlphabets
for character in source:
sourceCharacterCounter[ord(character)-ord('a')] += 1
for character in target:
targetCharacterCounter[ord(character)-ord('a')] += 1
for count in range(numberOfAlphabets):
if sourceCharacterCounter[count] != targetCharacterCounter[count]:
return False
return True
ord() function returns the integer representation of unicode character.
ord('a') is equal to 97.
ord('z') is equal to 122.
We created two arrays with size 26 and initialized with all 0’s.
[0,0,0.....,0] // 26 size
Let’s say our source string is cat.
for character in source:
sourceCharacterCounter[ord(character)-ord('a')] += 1
# [a,b,c,,,,,,,t,,,,,z]
# [1,0,1,,,,,,,1,,,,,0]
ord('c')-ord('a') represents index of character c.
sourceCharacterCounter[ord('c')-ord('a')] is nothing but number of occurrences of character c.
To understand further print both sourceAlphabetCounter and targetAlphabetCounter arrays is using Python’s print function.
#CheckIfStringsAreAnagram("anagram", "nagaram")
print(sourceAlphabetCounter)
print(targetAlphabetCounter)
"""
[3 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0]
[3 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0]
"""
If both array counts are same then both strings are anagrams.
Let’s improve the solution further.
Do we really need two counter arrays? No
Instead we can create only one counter array, then increase the count of each character in one string i.e, source and decrease the count of character in other string i.e.,target.
And if all values in the counter array are zero, then both strings are anagrams.
def CheckIfStringsAreAnagram(source: str, target: str) -> bool:
if len(source) != len(target):
return False
numberOfAlphabets = 26
characterCounter = [0]*numberOfAlphabets
for index in range(len(source)):
characterCounter[ord(source[index])-ord('a')] += 1
characterCounter[ord(target[index])-ord('a')] -= 1
for count in characterCounter:
if count != 0:
return False
return True
We will slightly change the implementation further.
Instead of loop through all characters in both strings, we can increase the character count of source string in one loop, and in other loop decrease the destination character count.
If the count becomes less than 0 we can say that both strings are not anagram as destination string have few extra characters.
def CheckIfStringsAreAnagram(source: str, target: str) -> bool:
if len(source) != len(target):
return False
numberOfAlphabets = 26
characterCounter = [0]*numberOfAlphabets
for index in range(len(source)):
characterCounter[ord(source[index])-ord('a')] += 1
for index in range(len(source)):
characterCounter[ord(target[index])-ord('a')] -= 1
if(characterCounter[ord(target[index])-ord('a')]<0):
return False
return True
Complexity
Time Complexity is O(n)
Where n is the length of the string.
Space Complexity is O(n)
Approach 3: Using Hash Table
If strings contains unicode characters (not only alphabets), we cannot use fixed size integer array.
Instead of that we should Hash table for the counters.
In Python dictionary implements a hash table.
So we will create two dictionary variables to store the character count.
func CheckIfStringsAreAnagram(source string, target string) bool {
if len(source) != len(target) {
return false
}
sourceDictionary, targetDictionary = {}, {}
for character in source:
sourceDictionary[character] = sourceDictionary.get(character, 0) + 1
for character in target:
targetDictionary[character] = targetDictionary.get(character, 0) + 1
return sourceDictionary == targetDictionary
}
Approach 4: Using Counter() function in collections.
The most simple way to solve the problem is to use Python’s Counter() function.
Counter() function counts the occurrences characters and stores as dictionary keys and their count as dictionary value.
Counter() function is part of collections.
print(Counter("anagram"))
## Outpur
## Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})
So we can pass both strings to Counter() function to check whether they are anagrams or not.
def CheckIfStringsAreAnagram(source: str, target: str) -> bool:
if len(source) != len(target):
return False
from collections import Counter
return Counter(source)==Counter(target)
Complexity
Time Complexity is O(n)
Where n is the length of the string.
Space Complexity is O(n)
Summary
We learnt different ways to check if two strings are anagrams or not in Python language.
In your daily projects you can use built in functions like sorted() or counter() to check if strings are anagrams or not.
Otherwise use character counting approach.
- Use frequency counter approach as it’s simple and easy to understand.
- Use Hash table approach if the strings contains unicode characters.