> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/data-structure/49.group-anagrams.md).

# 49.Group-Anagrams

## 49. Group Anagrams

## 题目地址

<https://www.lintcode.com/problem/anagrams>

<https://leetcode.com/problems/group-anagrams/>

## 题目描述

```
Given an array of strings, group anagrams together.

Example:

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

Note:
All inputs will be in lowercase.
The order of your output does not matter.
```

## 代码

### Approach 1: Categorize by Sorted String

Map => key: sort

**Complexity Analysis**

* Time Complexity: &#x4F;*(\_N\_K\_log\_K*), where *N* is the length of `strs`, and *K* is the maximum length of a string in `strs`. The outer loop has complexity &#x4F;*(\_N*) as we iterate through each string. Then, we sort each string in &#x4F;*(\_K\_log\_K*) time.
* Space Complexity: &#x4F;*(\_N\_K*), the total information content stored in `ans`.

```java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    if (strs.length == 0) return new ArrayList();

    Map<String, List> ans = new HashMap<String, List>();
    for (String s : strs) {
      char[] chs = s.toCharArray();
      Arrays.sort(chs);
      String key = String.valueOf(chs);
      if (!ans.containsKey(key)) {
        ans.put(key, new ArrayList());
        ans.get(key).add(s);
      } 
    }
    return new ArrayList(ans.values());
  }

}
```

Approach #2 Categorie by Count

```java
class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
    if (strs.length == 0) return new ArrayList();
    Map<String, List> ans = new HashMap<String, List>();
    int[] count = new int[26];
    for (String s : strs) {
      Arrays.fill(count, 0);
      for (char c : s.toCharArray()) {
        count[c - 'a']++;
      }
      StringBuilder sb = new StringBuilder("");
      for (int i = 0; i < 26; i++) {
        sb.append('#');
        sb.append(count[i]);
      }
      String key = sb.toString();
      if (!ans.containsKey(key)) {
        ans.put(key, new ArrayList());
        ans.get(key).add(s);
      }
    }

    return new ArrayList(ans.values());
  }
}
```

Approach #3

```java
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
   List<List<String>> result = new ArrayList<List<String>>();
    if (strs == null) return result;

    Map<String, ArrayList<String>> multiMap = new HashMap<String, ArrayList<String>>();
    for (String str : strs) {
      char[] strChar = str.toCharArray();
      Arrays.sort(strChar);
      String strSorted = String.valueOf(strChar);
      if (multiMap.containsKey(strSorted)) {
        ArrayList<String> aList = multiMap.get(strSorted);
        aList.add(str);
        multiMap.put(strSorted, aList);
      } else {
        ArrayList<String> aList = new ArrayList<String>();
        aList.add(str);
        multiMap.put(strSorted, aList);
      }
    }

    // add List group to result
    Set<String> keySet = multiMap.keySet();
    for (String key : keySet) {
      ArrayList<String> aList = multiMap.get(key);
      Collections.sort(aList);
      result.add(aList);
    }

    return result;
  }
}
```