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"].

method1.

brute-force. compare one-by-one O(n^2)

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        // write your code here

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

        HashSet<Integer> isVisited = new HashSet<>();

        for (int i = 0; i < strs.length; i++) {

            for (int j = i + 1; j < strs.length; j++) {

                if (!isAnagrams(strs[i], strs[j])) {
                    continue;
                }

                if (!isVisited.contains(i)) {
                    ans.add(strs[i]);
                    isVisited.add(i);
                }

                if (!isVisited.contains(j)) {
                    ans.add(strs[j]);
                    isVisited.add(j);
                }
            }
        }
        return ans;
    }


    public boolean isAnagrams(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return false;
        }

        if (s1.length() != s2.length()) {
            return false;
        }

        int[] count = new int[256];
        for (int i = 0; i < s1.length(); i++) {
            count[(int) s1.charAt(i)]++;
        }

        for (int i = 0; i < s2.length(); i++) {
            count[(int) s2.charAt(i)]--;
            if (count[(int) s2.charAt(i)] < 0) {
                return false;
            }
        }

        return true;

    }
}

metnod 2

1. make the int array to store the count of each character (26)
2. calculate the hash value of the array. constant a, constant b, for each count, hash = a * hash + count[i], a *= b
3. use hash value of each string as key and the ArrayList of string as value, check if a hash is already a key, if so, add the value into the list of the key, if not create the key as hash, and add the value
4. go throught the value of the map and addAll the list that contains more than 1 element.

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        // write your code here
        List<String> ans = new ArrayList<>();
        HashMap<Integer, ArrayList> map = new HashMap<>();
        for (String cur : strs) {
            int[] count = new int[26];
            for (int i = 0; i < cur.length(); i++) {
                count[cur.charAt(i) - 'a']++;
            }

            int hash = getHash(count);
            if (!map.containsKey(hash)) {
                ArrayList<String> list = new ArrayList<>();
                map.put(hash, list);
            }

            map.get(hash).add(cur);
        }

        for (ArrayList<String> list : map.values()) {
            if (list.size() > 1) {
                ans.addAll(list);
            }
        }

        return ans;


    }

    private int getHash(int[] count) {
        int a = 324234;
        int b = 2121;
        int hash = 0;
        for (int num : count) {
            hash = a * hash + num;
            a *= b;
        }

        return hash;
    }


}