> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/onsite-ii/171anagrams.md).

# 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;
    }
```