💬 Discord
Sign In
NeetCode #40LC-49MediumArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#40 · #49 · Group Anagrams(字母异位词分组)

📌 Problem Statement & Constraints

Given an array of strings strs, group the anagrams together. Return the groups in any order. Constraints: 1 <= strs.length <= 10^4, 0 <= strs[i].length <= 100; each string contains only lowercase English letters.

💡 Core Algorithmic Approaches

  1. Anagrams share the same multiset of characters, so any canonical form of that multiset works as a hash key.
  2. Option A: sort each string -- the sorted string is the key. Cost per string is O(k log k).
  3. Option B (better): build a 26-length count vector per string and use its tuple as the key. Cost per string is O(k).
  4. Group by appending to groups[key], then return the values. The tuple is required because lists are unhashable.

💻 Benchmark Python3 Implementation

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        groups = defaultdict(list)
        for s in strs:
            # canonical key: 26-dimensional character-count vector
            key = [0] * 26
            for ch in s:
                key[ord(ch) - 97] += 1
            groups[tuple(key)].append(s)      # tuple is hashable
        return list(groups.values())


# Alternative key: the sorted string (shorter to write, slightly slower)
class Solution2:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        groups = defaultdict(list)
        for s in strs:
            groups["".join(sorted(s))].append(s)
        return list(groups.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * k) with the counting key, where n is the number of strings and k the maximum length. The sorted-key variant is O(n * k log k).
💾 Space Complexity
O(n * k) for the output plus the grouping structure; the count vector itself is O(1) extra per string.

⚠️ Interview Pitfalls & Follow-ups

  • Using a list as the dictionary key: raises TypeError: unhashable type: 'list'. Convert to tuple.
  • Using the sorted string without joining: sorted(s) returns a list, which is again unhashable.
  • Assuming the empty string is special: "" has an all-zero count vector and groups with other empty strings; no special case needed.
  • Trying to compare pairwise with a custom anagram test: O(n^2 * k) and far more code.