Medium

Group Anagrams

037

Group anagrams together. Return each group sorted internally, and return groups ordered by their first string.

EXAMPLES

Example 1

Input
{
  "strs": [
    "eat",
    "tea",
    "tan",
    "ate",
    "nat",
    "bat"
  ]
}

Output
[
  [
    0,
    1,
    3
  ],
  [
    2,
    4
  ],
  [
    5
  ]
]

FUNCTION SHAPE

strs: stringArray→intMatrix

SOLUTION NOTE

We can group anagrams using their sorted word as key, and append the original word as part of the value list. Here n = len(strs), m = average string length.

Reveal reference solution +

pythonREFERENCE

# Method 1: Use sorted word as key
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagram_to_words = defaultdict(list)
    for word in strs:
        anagram_to_words[tuple(sorted(word))].append(word)
    return list(anagram_to_words.values())

# Method 2: Use sorted counter as key
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagram_to_words = defaultdict(list)
    for word in strs:
        anagram_to_words[tuple(sorted(Counter(word).items()))].append(word)
    return list(anagram_to_words.values())

TimeO(n * m log m)

SpaceO(n * m)

Open on LeetCode ↗