Question:
Given two strings s1 and s2, check if both the strings are anagrams of each other.
Examples:
Input : s1 = "listen"
s2 = "silent"
Output : The strings are anagrams.
Input : s1 = "dad"
s2 = "bad"
Output : The strings aren't anagrams.
Solution:
Method #1 : Using sorted() function
Python provides a inbuilt function sorted() which does not modify the original string, but returns sorted string.
Below is the Python implementation of the above approach:
Python
# function to check if two strings are# anagram or notdef check(s1, s2): # the sorted strings are checked if(sorted(s1)== sorted(s2)): print("The strings are anagrams.") else: print("The strings aren't anagrams.") # driver code s1 ="listen"s2 ="silent"check(s1, s2) |
The strings are anagrams.
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2 : Using Counter() function
- Count all the frequencies of 1st string and 2 and using counter()
- If they are equal then print anagram
Python3
# Python3 program for the above approachfrom collections import Counter# function to check if two strings are# anagram or notdef check(s1, s2): # implementing counter function if(Counter(s1) == Counter(s2)): print("The strings are anagrams.") else: print("The strings aren't anagrams.")# driver codes1 = "listen"s2 = "silent"check(s1, s2) |
The strings are anagrams.
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #3: Using Inbuilt List and Sort() Methods
Taking 2 User Inputs and appending to a list and then sorting the elements in a list and it checks If they are equal then print anagram else aren’t anagrams
Python3
## Example 1 for "The strings are anagrams."#Declare Inputsinp1 = "listen"inp2 = "silent"#Sort Elementsx = [inp1[i] for i in range(0,len(inp1))]x.sort()y = [inp2[i] for i in range(0,len(inp2))]y.sort()# the sorted strings are checkedif (x == y):print("The strings are anagrams.")else: print("The strings aren't anagrams.")## Example 2 for "The strings aren't anagrams."#Declare Inputsinp1 = "listen"inp2 = "silenti"#Sort Elementsx = [inp1[i] for i in range(0,len(inp1))]x.sort()y = [inp2[i] for i in range(0,len(inp2))]y.sort()# the sorted strings are checkedif (x == y):print("The strings are anagrams.")else: print("The strings aren't anagrams.") |
The strings are anagrams. The strings aren't anagrams.
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
Method #4: Using a dictionary to achieve constant time complexity
A dictionary in python provides constant time lookup. The algorithm is very simple and works like this:
- Loop through the characters of the two strings simultaneously. Suppose c1 is the current character of the first string and c2 the current character of the second string.
- For each of c1 and c2, say c, do the following:
- If c is not present as a key in the dictionary, then create a dictionary entry with the key being c and the value being
- 1 if c is c1 (current character of the first string)
- -1 if c is c2 (current character of the second string)
- If c is present as a key in the dictionary, then instead of creating a new key-value pair, just increase or decrease the value in a similar way as in the previous step.
- If c is not present as a key in the dictionary, then create a dictionary entry with the key being c and the value being
- After that, loop through the dictionary. If there is a key-value pair in the dictionary where it’s value is different than 0, the two strings and not anagram. Otherwise, they are.
Python3
def anagrams(inp1: str, inp2: str) -> bool: # if the length of the two strings is not the same, they are not anagrams. if len(inp1) != len(inp2): return False # initialize the dictionary counts = {} # loop simultaneously through the characters of the two strings. for c1, c2 in zip(inp1, inp2): if c1 in counts.keys(): counts[c1] += 1 else: counts[c1] = 1 if c2 in counts.keys(): counts[c2] -= 1 else: counts[c2] = -1 # Loop through the dictionary values. # if the dictionary contains even one value which is # different than 0, the strings are not anagrams. for count in counts.values(): if count != 0: return False return True# test the implementationdef main(): inp1 = "listen" inp2 = "silent" if anagrams(inp1, inp2): print(f"{inp1} and {inp2} are anagrams") else: print(f"{inp1} and {inp2} are not anagrams")if __name__ == "__main__": main() |
listen and silent are anagrams
Time Complexity: O(n) since we have to loop through all characters for both of the strings.
Auxiliary Space: O(n) in the worst case where all letters are different for even one of the string inputs. If both string inputs have eg. 4 letters out of which only 2 are different (eg. “SaaS” and “SaSa”), the space needed would be O(n/2)
Approach#5:using list and dictionary
Algorithm
1.Convert both strings to lists of characters.
2.Create a dictionary to count the frequency of each character in the first string.
3.Iterate over the characters of the second string and decrement the corresponding count in the dictionary.
4.If all counts in the dictionary are zero, the strings are anagrams.
Python3
s1 = "dad"s2 = "bad"char_list_1 = list(s1)char_list_2 = list(s2)char_count = {}for char in char_list_1: if char not in char_count: char_count[char] = 0 char_count[char] += 1for char in char_list_2: if char not in char_count: print("The strings are not anagrams.") break char_count[char] -= 1else: for count in char_count.values(): if count != 0: print("The strings are not anagrams.") break else: print("The strings are anagrams.") |
The strings are not anagrams.
Time complexity: O(n), where n is the length of the longer string.
Space complexity: O(n), where n is the length of the longer string.
