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

What is Anagram?

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

Tags

Hash Table String Uber 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;
    }