Online Course Discussion Forum

Intro to algorithm anagram function problem

Picture of John Lensmire
Re: Intro to algorithm anagram function problem
by John Lensmire - Tuesday, June 14, 2022, 2:11 PM

I'll focus most on the second code.

I would describe the general idea of the algorithm is as follows: Looping through the 1st string letter by letter, we look in the 2nd string for a matching letter. To be anagrams, all the letters in the 1st string need to match with a letter in the 2nd.

Key Difficulties:

1) What about repeated letters? A first approach might just look for matching letters, without worrying about a repeated letter in the 1st string only appearing once in the second. Without being careful, this is how you'd get "tooth" and "oooth" being considered anagrams.

Fix for 1): Once a matching letter in the second string, that position is replaced by None, so it can't be matched twice.

It seems like you are okay with this portion, but let us know if you have questions here too.

2) How can we know that we have a match for ALL the letters in the first word? If we start by checking that both strings have the same length, then it is enough to ensure that each letter in the 1st string has a matching letter in the 2nd. (Here I'm assuming 1) has already been dealt with, so here the first "o" matches with the first "o", etc.)

Note then that as soon as we have ONE letter that doesn't match, we already know that the answer is False. This leads us to:

Fix for 2): As soon as we find a letter that doesn't match (meaning we've finished the "inner loop") we can return the answer False. This is what the variable stillok accomplishes. As the outer loop proceeds to move on the next letter, we also check that the previous letter was okay. If it's not, there's no use continuing, so we just stop and return the answer.

Additional Notes:

i) I'm not quite of the role of the variable found. Basically you just can use the break command to exit the inner loop once you find the letter.

ii) For the stillok variable, it's somewhat unnecessary to set it to False everytime there's a non-match. In cases like this, it might be easiest to have it set to False once at the beginning (before the loop), and then it's only changed to True once there is a match. This is fine to do because of the break command, as we stop looking as soon as there is a match.

Hope this helps!