Problem

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

Notice

All inputs will be inlower-case

Have you met this question in a real interview?

Yes

Example

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

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

错误思路(hash)

• hash所有字符串放在一个数组中, 并且用hashmap统计同一个hashcode的个数

• 遍历原数组, 若它的code对应hashmap中的value大于1, 那么便是anagrams

• 时间复杂度: O(n * len)

• 出错原因:

  • hash = hash + 378551 * num;

  • 这个不可避免会出现不同字符串, 同一个hashcode的情况

  • 所以不应该hash字符., 应该对每个字符串每一个字符出现的个数进行hash;

正确思路(hash)

• 因为我们不考虑字符串字符出现的顺序, 于是我们开一个大小26的数组统计该字符串每个字符出现的个数
• hash整个统计个数的数组
• 时间复杂度: O(n * len)

    /**
     *  1. hashcode everything
     *  2. overwrite equals, 
     *     ["lint", "intl", "inlt", "code"]
     *  3. [1,      1,      1,      2]
     *          1, 3
     *          2, 1
     *  
     */
    public List<String> anagrams(String[] strs) {
        List<String> res = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return res;
        }

        int[] codes = new int[strs.length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            int[] count = new int[26];
            for (char ch: strs[i].toCharArray()) {
                count[ch - 'a']++;
            }
            codes[i] = hash(count);
            if (map.containsKey(codes[i])) {
                map.put(codes[i], map.get(codes[i]) + 1);
            } else {
                map.put(codes[i], 1);
            }
        }
        for (int i = 0; i < strs.length; i++) {
            if (map.get(codes[i]) > 1) {
                res.add(strs[i]);
            }
        }
        return res;
    }

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

思路2(排序)

    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray(); 
            Arrays.sort(arr);
            String s = String.valueOf(arr);
            if (!map.containsKey(s)) {
                ArrayList<String> list = new ArrayList<String>();
                map.put(s, list);
            }
            map.get(s).add(strs[i]);
        } 
        for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
            if (entry.getValue().size() >= 2) {
                result.addAll(entry.getValue());
            }
        }
        return result;
    }