Given an array of strings, group anagrams together.

For example, given:["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:All inputs will be in lower-case.

Solution: 3种方法:1.把string变为char array后sort了再变为string,再放进hashmap;2.统计string出现字符的种数和个数,计算hash值;3.每个字符对应一个质数,相乘得到hash值

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<List<String>>();
        if(strs == null || strs.length == 0){
            return ans;
        }

        HashMap<Integer, ArrayList<Integer>> hashmap = new HashMap<Integer, ArrayList<Integer>>();
        //solution1: sort char array
        // for(int i = 0; i < strs.length; i++){
        //     char[] chars = strs[i].toCharArray();
        //     Arrays.sort(chars);
        //     String arranged = new String(chars);
        //     if(!hashmap.containsKey(arranged)){
        //         ArrayList<Integer> list = new ArrayList<Integer>();
        //         list.add(i);
        //         hashmap.put(arranged, list);
        //     } else{
        //         hashmap.get(arranged).add(i);
        //     }
        // }
        for(int i = 0; i < strs.length; i++){
            int[] count = new int[26];
            for(int j = 0; j < strs[i].length(); j++){
                count[strs[i].charAt(j) - 'a']++;
            }
            int hash = getHash(count);
            if(!hashmap.containsKey(hash)){
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(i);
                hashmap.put(hash, list);
            } else{
                hashmap.get(hash).add(i);
            }
        }
        for(Map.Entry<Integer, ArrayList<Integer>> entry : hashmap.entrySet()){
            List<String> anagrams = new ArrayList<String>();
            for(Integer i : entry.getValue()){
                anagrams.add(strs[i]);
            }
            ans.add(anagrams);
        }
        return ans;
    }
    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 static List<List<String>> groupAnagrams(String[] strs) { 
   int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z

            List<List<String>> res = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (String s : strs) {
                int key = 1;
                for (char c : s.toCharArray()) {
                    key *= prime[c - 'a'];
                }
                List<String> t;
                if (map.containsKey(key)) {
                    t = res.get(map.get(key));
                } else {
                    t = new ArrayList<>();
                    res.add(t);
                    map.put(key, res.size() - 1);
                }
                t.add(s);
            }
            return res;
    }

results matching ""

    No results matching ""