# 171.Anagrams

## 1.Description(Medium)

Given an array of strings, return all groups of strings that are anagrams.

### Notice

All inputs will be in **lower-case**

**Example**

Given`["lint", "intl", "inlt", "code"]`, return`["lint", "inlt", "intl"]`.

Given`["ab", "ba", "cd", "dc", "e"]`, return`["ab", "ba", "cd", "dc"]`.

[**Challenge**](https://www.lintcode.com/en/problem/anagrams/#challenge)

What is Anagram?

* Two strings are anagram if they can be the same after change the order of characters.

[**Tags**](https://www.lintcode.com/en/problem/anagrams/#tags)

[Hash Table](https://www.lintcode.com/tag/hash-table/) [String](https://www.lintcode.com/tag/string/) [Uber](https://www.lintcode.com/tag/uber/) [Facebook](https://www.lintcode.com/tag/facebook/)

## 2.Code

Version 1:排序哈希表法：时间 O(NKlogK) 空间 O(N) ; 我们有n个字符串，字符串最大长度是k(排序用klogk)

判断两个词是否是变形词，最简单的方法是将两个词按字母排序，看结果是否相同。这题中我们要将所有同为一个变形词词根的词归到一起，最快的方法则是用哈希表。所以这题就是结合哈希表和排序。

我们将每个词变成数组，然后为数组排序，再变回string.

根据这个键值，找到哈希表中相应的列表，并添加进去。

为了满足题目字母顺序的要求，我们输出之前还要将每个列表按照内部的词排序一下。可以直接用Java的Collections.sort()这个API。

**注意在char\[] 变回string的时候不能用.toString();**

**这个方法过不了当input是\["",""]，output是\[], 但实际应该是\["",""]**

应该用**String key=String.valueOf(current)**; 或者**String key=new String(current);**

## String.valueOf 和toString()的区别：

When argument is null , the **String**.**valueOf** returns "null" ,

but Object.**toString** throws NullPointerException , that's the only difference.

```
 public List<String> anagrams(String[] strs) {

        List<String> result=new ArrayList<String>();
        if(strs==null || strs.length==0){
            return result;
        }

        HashMap<String,List<String>> map=new HashMap<>();
        for(int i=0;i<strs.length;i++){
            //fetch this word and make it array then sort it then remake a string
            char[] current=strs[i].toCharArray();
            Arrays.sort(current);

            //不能用 String key=current.toString();
            //或者String key=String.valueOf(current);
            String key=new String(current);

            if(map.containsKey(key)){
                map.get(key).add(strs[i]);
            }else{
                List<String> word=new ArrayList<String>();
                word.add(strs[i]);
                map.put(key, word);
            }       
        }


        for(List<String> element:map.values()){
            if(element.size()>1){
                result.addAll(element);
            }
        }
        return result;
    }
```

Version 2: 为每一个单词建立一个hash值，用hash值存放进hashmap.

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

    public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> result = new ArrayList<String>();
        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()) {
            if (tmp.size() > 1) {
                result.addAll(tmp);
            }
        }

        return result;
    }
```


---

# Agent Instructions: 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:

```
GET https://junnie.gitbook.io/amazon-mock-interview/onsite-ii/171anagrams.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.