Group Anagrams

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
• An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Solution

• Naive would be to compare every string against each other.
  • That would be very slow: O(n^2 * k), k being the string length.
• Better solution is to compute a character frequency, and use that as a hash key.
  • Strings with the same character frequencies are anagrams.
  • Time complexity would be O(n * k).

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # time complexity: O(n * k)
        # space complexity: O(n * k)
        anagrams = defaultdict(list)
 
        for s in strs:
            count = [0] * 26
 
            for c in s:
                count[ord(c) - ord('a')] += 1
 
            anagrams[tuple(count)].append(s)
 
        return list(anagrams.values())

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───