49 Group Anagrams

Given an array of strings, group anagrams together.

Example:

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

Output:

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

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

• //

  time : O(m * n) space : O(n) counting sort

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] sch = str.toCharArray();
            int[] arr = new int[26];
            String s = "";
            for (char c : sch) {
                arr[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                int num = arr[i];
                char p = (char)(i + 'a');
                s += String.valueOf(num);
                s += String.valueOf(p);
            }
            if (map.containsKey(s)){
                map.get(s).add(str);
            }else {
                map.put(s, new ArrayList<>());
                map.get(s).add(str);
            }
        }
        for (List<String> value : map.values()) {
            ans.add(value);
        }
        return ans;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length== 0) {
            return ans;
        }
        int[] prime = new int[26];
        int curt = 2;
        for (int i = 0; i < 26; i++) {
            while (!isPrime(curt)) {
                curt++;
            }
            prime[i] = curt;
            curt++;
        }
        Map<Integer, Integer> map = new HashMap<>(); // key -> indice
        for (String str : strs) {
            int key = 1;
            for (char c : str.toCharArray()) {
                key *= prime[c - 'a'];
            }
            List<String> part;
            if (map.containsKey(key)) {
                part = ans.get(map.get(key));
            }else {
                part = new ArrayList<>();
                ans.add(part);
                map.put(key, ans.size() - 1);
            }
            part.add(str);
        }
        return ans;
    }
    public boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Prime Number

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