Skip to content

10.02. Group Anagrams

Description

Write a method to sort an array of strings so that all the anagrams are in the same group.

Note: This problem is slightly different from the original one the book.

Example:


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

Output:

[

  ["ate","eat","tea"],

  ["nat","tan"],

  ["bat"]

]

Notes:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Solutions

Solution 1: Hash Table

  1. Traverse the string array, sort each string according to character lexicographical order, and get a new string.
  2. Use the new string as key and [str] as value, and store them in the hash table (HashMap<String, List<String>>).
  3. When the same key is encountered in subsequent traversals, add it to the corresponding value.

Take strs = ["eat", "tea", "tan", "ate", "nat", "bat"] as an example. At the end of the traversal, the state of the hash table is:

key value
"aet" ["eat", "tea", "ate"]
"ant" ["tan", "nat"]
"abt" ["bat"]

Finally, return the value list of the hash table.

The time complexity is $O(n\times k\times \log k)$, where $n$ and $k$ are the length of the string array and the maximum length of the string, respectively.

1
2
3
4
5
6
7
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            k = ''.join(sorted(s))
            d