> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter_1_combination_and_permutation/problem_49_group_anagrams.md).

# Problem 49: Group Anagrams

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

## 思路

* 直观的思路就是，同一类的几个字符串之间，他们只是顺序不同，每一个字母的个数其实是相同的。所以我们可以用一个 26 个字母组成的数组 count 来记录不同的字符串
* 同一类的字符串，给他们一个相同的 hash 值。注意：计算 hash 值的时候，要用质数

```java
/* 
    非最优解法，有额外空间
*/
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<String> path = new ArrayList<String>();
        List<List<String>> rst = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return rst;
        }

        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            } 
            map.get(key).add(s);
        }

        for (String s : map.keySet()) {
            path = new ArrayList<String>();
            path = map.get(s);
            Collections.sort(path);
            rst.add(path);
        }

        return rst;

    }
}
```

```java
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<String> path = new ArrayList<String>();
        List<List<String>> result = new ArrayList(path);
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();

        for (String str : strs) {
            int[] count = new int[26];

            for (int i = 0; i < str.length(); i++) {
                count[str.charAt(i) - 'a']++;
            }
            int hash = getHash(count);
            if (!map.containsKey(hash)) {
                map.put(hash, new ArrayList<String>());
            }
            map.get(hash).add(str);
        }

        for (ArrayList<String> tmp : map.values()) {
            result.add(tmp);
        }

        return result;
    }

    private int getHash(int[] count) {
        int hash = 0;
        int a = 378551;
        int b = 63689;
        for (int num : count) {
            hash = a * hash + num;
            a = a * b;
        }
        return hash;
    }
}
```

## 易错点

1. 计算 hash code

   ```java
   private int getHash(int[] count) {
        int hash = 0;
        int a = 378551;
        int b = 63689;
        for (int num : count) {
            hash = a * hash + num;
            a = a * b;
        }
        return hash;
   }
   ```

   ![](/files/-Lpv9uelS1pr344ClKaD)
2. 记录每个字母出现的次数

   ```java
   for (int i = 0; i < str.length(); i++) {
          count[str.charAt(i) - 'a']++;
   }
   ```
3. 加入 str 到 map

   ```java
   map.get(hash).add(str);
   ```

   这里是其实是需要解释一下的：首先 map 的格式是这样的 `HashMap<Integer, ArrayList<String>>`，key 是 Integer，value 是 `ArrayList<String>`，所以当 `map.get(hash)`的时候，得到的其实是一个 ArrayList，再往里面加东西的时候，用 add() 方法
4. 逻辑结构

   ```java
   if (!map.containsKey(hash)) {
       map.put(hash, new ArrayList<String>());
   }
   map.get(hash).add(str);
   ```

   之前用了 if - else 的结构，导致出现错误。这里不是两者取其一的问题，而是先判断有没有这个 key，没有的话先构造一个 key，然后再把字符串加进去。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://liuyang89116.gitbook.io/my-leetcode-book/chapter_1_combination_and_permutation/problem_49_group_anagrams.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.