String Processing in Python: Is Anagram

[@MasteringProgrammingTapAway]

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

[@LucidProgramming]

Thank you! I appreciate that comment. I hope these videos are helpful, and thanks again for watching!

[@goldy5858]

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.

[@LucidProgramming]

Sure, you could do that to simplify the code slightly. Cheers, and thanks for watching!

[@gevorggalstyan6392]

Beautiful solution. Thank you for all your videos.

[@LucidProgramming]

Cheers, and thanks for watching!

[@aghiadalzein3069]

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.

[@LucidProgramming]

Sure, you could.

[@MattWiener1]

I came to the comments to look for this. if i is not in ht for s2, false. once you finish checking s2 you know you're done.

[@mahammadodj]

thank you so much

[@LucidProgramming]

No problem, thanks for watching!

[@finnley-7188]

Hey do you know how to make this into a function

[@LucidProgramming]

It's already in a function, is it not?

[@DHAiRYA2801]

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?

[@LucidProgramming]

Seems fine to me, don't see a problem.

[@pradeepkumar-qo8lu]

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

[@LucidProgramming]

Hi Pradeep. You could do that, but that would give you a hit in time and space complexity. Does the achieve the same thing though!

[@pythonenthusiast9292]

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??

[@LucidProgramming]

But we need to set it back to being equal to "1", right?

[@marcobroca4020]

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")

[@LucidProgramming]

There is no way that set has a complexity of O(1).

[@brendancheong7738]

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

[@LucidProgramming]

Do you have any guesses?

[@brendancheong7738]

@@LucidProgramming Im gonna go on a wild guess and say O(n)

[@LucidProgramming]

@@brendancheong7738 Yeah, both for time and space.

[@linusjohansson3164]

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?

[@LucidProgramming]

Thanks! And yeah, MIT opencourseware has a great course on algorithms that would be right up your alley!

[@linusjohansson3164]

Thank you! @@LucidProgramming

[@LucidProgramming]

@@linusjohansson3164 Of course, and thank you for the support!

[@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.

[@vincentrusso6563]

Time-wise, that does seem to be beneficial, but in space you'll be taking on some extra when you initialize the dictionary. For this problem on such a small size, it's not a big deal of course, but for larger problem sizes it might be a factor you're concerned about. Cheers, and thanks as always for your comments!

[@KippiExplainsStuff]

@@vincentrusso6563 Yes. Space might be an issue. Good point. My thought is, with modern computing, where space is almost never an issue anymore (unless you are working on RT systems with tiny RAM or something), I'd rather "waste" a little space rather than time. Obviously this should be viewed on a case to case question.

[@LucidProgramming]

@@KippiExplainsStuff Right, good point. Surely, especially for this problem, space will not be an issue. However, in an interview setting, it is good to point out that you are aware of the space requirements especially if they happened to be much larger than this particular example. Thanks for the comment, as always!

[@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!

[@LucidProgramming]

The general idea is fine, but the runtime of your solution is worse.

[@shonnoronha]

@@LucidProgramming Thanks for replying, I'm just a beginner with no prior knowledge of programming, going through your playlist ,your videos are really good ! Keep going !

[@LucidProgramming]

@@shonnoronha Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@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

[@LucidProgramming]

I think there are some edge cases for which this doesn't work.

[@rizetothemoon]

@@LucidProgramming I had the same thought as @Lei Zhang. If s2 contains a char. which has not been found in s1 (having an entry in the hash table), can't we automatically conclude s2 is not an anagram of s1? Do you mind sharing those edge cases?

[@LucidProgramming]

@@rizetothemoon Ah okay, I think I understand what Lei was proposing. Yes, of course, you can have an early exit condition like the one you are describing there, I don't see any issue with that. Sorry for the confusion!

[@rizetothemoon]

@@LucidProgramming thanks for the reply. I have watched all your data structure and algo videos. Appreciate the work you've done!

[@LucidProgramming]

@@rizetothemoon Cheers, I appreciate that, Roger!

[@jillward6256]

Kodie an Kyler should be ok to use as an anagr

[@LucidProgramming]

You can use them to check, but those words would not be anagrams.

[@mohammedrilwan9050]

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

[@LucidProgramming]

Have you tried this with any success?