String Processing in Python: Is Anagram

In this video, we will be determining whether two strings are anagrams of each other.

Wikipedia article on Anagrams:

Simply, an anagram is when two strings can be written using the same letters.

Examples:
"rail safety" = "fairy tales"
"roast beef" = "eat for BSE"

It sometimes changes a proper noun or personal name into a sentence:

"William Shakespeare" = "I am a weakish speller"
"Madam Curie" = "Radium came"

Problem:
Two strings. Check if they are anagrams.

This video is part of a series on string processing and, specifically, on how these problems tend to show up in the context of a technical interview:

This video is also part of an "Algorithm" series. For more algorithm tutorials:

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[MasteringProgrammingTapAway]

I like how you include data structures and algorithms in your tutorials rather than just throwing the easiest solution.

[goldy]

First, thanks a lot for this algorithm course. I am not from CS background but your course is helping me a lot to understand the basics.
For the example, I think the two 'if' statements can be replaced by one 'if' to search for every letter of string two is in the hash table or not. If not, we can return false else true. No need for subtraction and checking for zeros.

[gevorggalstyan]

Beautiful solution. Thank you for all your videos.

[aghiadalzein]

I was wondering whether on the second for loop if the letter doesn't exist in ht we can return False directly(and save us from entering the third for loop), is not that right ??!!
Best regards.

[linusjohansson]

Great videos!
Subd!
Can you recommend a good source where i can learn about time and space of algorithms,
that comparison based sorting algorithms requries at least n log n time to sort
etc?

[pradeepkumar-qolu]

Why not use
sorted(s1)==sorted(s2) after processing the strings
Don't they achieve the same thing or am I missing something??

[DHAiRYA]

def anagram(a, b):
score = 0
for i in a:
if i in b:
score+=1
return score==len(a)

What is the problem here?

[pythonenthusiast]

In the second for loop, why is it important to put the else condition ?
as if the element is already not present in the dictionary then it is a new element and we can return false there itself right??

[marcobroca]

Nice video, thanks for taking time to do such a great job.

I have a doubt, could also set() function be a solution? since it has a time cmplexity of o(1).

def anagram(text1, text2):
text1, text2 = [i for i in text1.lower() if i.isalpha()], [i for i in text2.lower() if i.isalpha()]
if len(text1)==len(text2) and set(text1)==set(text2):
return True
return False

anagram("fairy tales? ", "Rail safety")

[KippiExplainsStuff]

Ok. Nice solution. Question:
Is it not even better (time wise) to initialize the dict by the 26 letters of the alphabet and the value as zero? This will cut down 2 if statements. Whenever you encounter a letter you simply do
ht[i] +=1
No matter if the letter has been previously found.

[finnley-]

Hey do you know how to make this into a function

[shonnoronha]

How about this we take s1 and s2 as input create and empty list l1. Loop through s1 if i in s1 and i also in s2 . Append to l1. If the length of l1 and s1 or s2 matches return True .if lenth does not match or both are empty string return False.
If it's wrong please correct me!

[bcej]

what is the time complexity of this algorithm? (since its faster than n log(n))

[larrybai]

In is_anagram()

for i in s2:
if i in ht:
ht[i]=ht[i]-1
else:
return False #other than ht[i]=1


Because if i is in s2 but not in s1, we can determine that s1 and s2 are not anagram

[mohammedrilwan]

we can return false if 'i not in ht'..while iterating in S2..isnt it ?

[jillward]

Kodie an Kyler should be ok to use as an anagr