Watched neetcode and some other videos on this problem and they sped through all of this code without properly explaining why we are doing what were doing. Happy to have found this video. Really solid explanation. Keep it up
I've done like this class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: counter = defaultdict(list) for s in strs: key = ''.join(sorted(s)) counter[key].append(s) return list(counter.values())
slight note. return statement should be "list(anagrams_dict.values())" since the question asks to return a list of a list and not dict_values. great solution anyways
for python 3, I needed to change the return to: `return [sorted(group) for group in anagrams_dict.values()]` Your code is so fast. thanks for the solution.
fantastic example to help learner to realize that dict and sets are not hashable, since almost everyone would have thought of using a set of sets (i did) or dict with keys as dict (like you did) and realize that it's not possible
tried your solution on problem 49 Greg. But it is not accepting this time. anagram_dict = defaultdict(list) for s in strs: count = [0] * 26 for i in s: count [ord(i)- ord('a')] +=1 key = tuple(count) anagram_dict[key].append(s) return anagram_dict.values() it return with a runtime error. with TypeError: dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]) is not valid value for the expected return type list ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ raise TypeError(str(ret) + " is not valid value for the expected return type list"); I tried the the one comment solution from Funtasticflutter that one worked. W
im confused about if the key isn't in the dictionary yet, it associates its value with an empty list. how does the first string in a list get added when the key isn't in the dictionary yet if it associates an empty list and not the appended string? hope this makes sense
Great question. He might have mis-spoken there. If it is not in dictionary it instantiates a list with the only element as the string. The solution with dict is below, and it is faster than the defaultdict solution: hashh = {} #hashh = defaultdict(list) for s in strs: count_arr = [0] * 26 for c in s: count_arr[ord(c)-ord('a')]+=1 keyy = tuple(count_arr) if keyy in hashh: hashh[keyy].append(s) else : hashh[keyy] = [s] return hashh.values()
my solution ..runtime 87 ms.....mem 19.3 MB def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagram_dict={} for s in strs: sorted_s= "".join(sorted(s)) if sorted_s in anagram_dict: anagram_dict[sorted_s].append(s) else: anagram_dict[sorted_s]=[s]
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Watched neetcode and some other videos on this problem and they sped through all of this code without properly explaining why we are doing what were doing. Happy to have found this video. Really solid explanation. Keep it up
Wow so happy that you enjoyed it!
just found this channel. your amazing man.
Awww thank you so much I really do appreciate it and I'm so glad it's been helpful 😊😊
I've done like this
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
counter = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
counter[key].append(s)
return list(counter.values())
slight note. return statement should be "list(anagrams_dict.values())" since the question asks to return a list of a list and not dict_values. great solution anyways
for python 3, I needed to change the return to: `return [sorted(group) for group in anagrams_dict.values()]`
Your code is so fast. thanks for the solution.
sorted function is not needed, group will do just fine
I solved this problem a week ago, but your method is much more attractive. Thank you for your job!!!!
You're very welcome 😁
fantastic example to help learner to realize that dict and sets are not hashable, since almost everyone would have thought of using a set of sets (i did) or dict with keys as dict (like you did) and realize that it's not possible
tried your solution on problem 49 Greg. But it is not accepting this time.
anagram_dict = defaultdict(list)
for s in strs:
count = [0] * 26
for i in s:
count [ord(i)- ord('a')] +=1
key = tuple(count)
anagram_dict[key].append(s)
return anagram_dict.values()
it return with a runtime error.
with
TypeError: dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]) is not valid value for the expected return type list
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
raise TypeError(str(ret) + " is not valid value for the expected return type list");
I tried the the one comment solution from Funtasticflutter that one worked. W
I love the solution. I am curious as to why using dict is faster than defaultdict
4:58 Note : ord is used to get the unicode of a charecter and not ascii value
dude you're my hero
hi :D, genuine question, why are you using an array then call tuple on it and not using a Counter and call tuple on it?
What’s the problem converting dict to str and pass it as a key?
im confused about if the key isn't in the dictionary yet, it associates its value with an empty list. how does the first string in a list get added when the key isn't in the dictionary yet if it associates an empty list and not the appended string? hope this makes sense
I think that is why there is a defaultdict. Check python docs for more on it
Great question. He might have mis-spoken there. If it is not in dictionary it instantiates a list with the only element as the string. The solution with dict is below, and it is faster than the defaultdict solution:
hashh = {}
#hashh = defaultdict(list)
for s in strs:
count_arr = [0] * 26
for c in s:
count_arr[ord(c)-ord('a')]+=1
keyy = tuple(count_arr)
if keyy in hashh:
hashh[keyy].append(s)
else :
hashh[keyy] = [s]
return hashh.values()
Very helpful!
my solution ..runtime 87 ms.....mem 19.3 MB
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_dict={}
for s in strs:
sorted_s= "".join(sorted(s))
if sorted_s in anagram_dict:
anagram_dict[sorted_s].append(s)
else:
anagram_dict[sorted_s]=[s]
return list(anagram_dict.values())
Looks great to me!!
And this is how Greg started GregGPT
Lmao
Why is the inside (m log m) ?
fastest sorting algo have time comp. m logm
and we are sorting each string here m is the length of string, which is different in each case
Holy cow, this one is NOT easy.
Yeah it's not easy lol
I don't think I'd need to learn this one ... lol
You should learn it it might be the most useful question out of all of them tbh
@@GregHogg I think it is useful, but would love to hear an explanation of why this could be the most useful one.