Hey, babybear4812. First off, love your videos! Secondly, wouldn't having a time complexity of O(nlogn) with the implementation of sorting be better than the O(nk) time complexity of counting characters? In the worst-case scenario for sorting, n = 10^4 and so log2(n) is only ~13. Whereas the worst-case scenario for counting characters is n = 10^4 and k = 100. [worst-case n and k taken from the constraints in the problem]. If I'm completely wrong, though, let me know lol. My code below uses the sorting method and I think it still looks clean and intuitive. class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: seen = defaultdict(list) for s in strs: sorted_s = ''.join(sorted(list(s))) # anagram group of word seen[sorted_s] += [s] # add word to anagram group in dictionary output = seen.values() return output
Hey, babybear4812. First off, love your videos! Secondly, wouldn't having a time complexity of O(nlogn) with the implementation of sorting be better than the O(nk) time complexity of counting characters? In the worst-case scenario for sorting, n = 10^4 and so log2(n) is only ~13. Whereas the worst-case scenario for counting characters is n = 10^4 and k = 100. [worst-case n and k taken from the constraints in the problem]. If I'm completely wrong, though, let me know lol. My code below uses the sorting method and I think it still looks clean and intuitive.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
seen = defaultdict(list)
for s in strs:
sorted_s = ''.join(sorted(list(s))) # anagram group of word
seen[sorted_s] += [s] # add word to anagram group in dictionary
output = seen.values()
return output
I guess we're comparing 10^6 vs. 10^5 worst case (give or take). Probably a valid point to bring up in your interview when you discuss both options :)