Neetcode For Fun - 1
Solving https://neetcode.io/problems/is-anagram . Started at 1:29 AM.
Let’s think about this for a minute.
A word ‘w1’ is an anagram of a word ‘w2’ if all the characters in w1 belong in w2. Duplicates included.
So the simplest solution would be to go through every letter in w1 and then check if it is there in w2. That’s a O(n^2) complexity because to check against the second string, each letter would have to be compared against. Let’s code it up :
1class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 anagram = True
4 for i in s:
5 if i not in t:
6 anagram = False
7 break
8 return anagram
9
Analysis level 2 :
The problem with this solution while it works in theory is that it checks for “membership” i.e. belonging-to-a-string but it doesn’t check if the number of times a character belongs in w1 is the same as in w2.
Therefore it would fail for
1s="xx"
2t="x"
Accounting for frequency of characters :
1class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 letter_counter_s = {i:s.count(i) for i in s}
4 letter_counter_t = {i:t.count(i) for i in t}
5 anagram = True
6 for k, v in letter_counter_s.items():
7 if k in letter_counter_t:
8 if letter_counter_t[k] != v:
9 anagram = False
10 break
11 else:
12 anagram = False
13 break
14 return anagram
Analysis level 3 :
Again, this Looks like it works but it fails when the first string is shorter than the second string. (Can you see why?)
Therefore, straight away rejecting the possibility of an anagram if the lengths of the strings don’t match -
1class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 if len(s) != len(t):
4 return False
5 letter_counter_s = {i:s.count(i) for i in s}
6 letter_counter_t = {i:t.count(i) for i in t}
7 anagram = True
8 for k, v in letter_counter_s.items():
9 if k in letter_counter_t:
10 if letter_counter_t[k] != v:
11 anagram = False
12 break
13 else:
14 anagram = False
15 break
16 return anagram
And that yielded the complete case -
Atleast functionally…. Let’s see on Leetcode how slow our solution is.
As expected, from a time complexity perspective, we’re trailing towards the end, beating only 5% of all solutions. So let’s examine this a little more.
What if instead of an array look-up , I used a get method? Would that help?
1class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 if len(s) != len(t):
4 return False
5 letter_counter_s = {i:s.count(i) for i in s}
6 letter_counter_t = {i:t.count(i) for i in t}
7 anagram = True
8 for k, v in letter_counter_s.items():
9 if letter_counter_t.get(k) != v:
10 anagram = False
11 break
12 return anagram
It did not.
1class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 if len(s) != len(t):
4 return False
5 tl = list(t)
6 for i in s:
7 if i in tl:
8 tl.remove(i)
9 else:
10 return False
11 return True
This got a little better (down from 5800 ms to 900 ms). But still poor.
2.15 AM I will continue this in the morning.