Group Anagrams

Problem Information

Material

Solution

Brute Force

We use the same optimal strategy to check if two strings are a Valid Anagram, then we just iterate the list and check if it groups with one element. 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();

        for (String s: strs) {
            boolean grouped = false;
            for (List<String> list: res) {
                if (isAnagram(list.get(0), s)) {
                    list.add(s);
                    grouped = true;
                }
            }

            if (!grouped) {
                List<String> list = new ArrayList<>();
                list.add(s);
                res.add(list);
            }
        }

        return res;
    }

    private boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;

        int[] count = new int[26];
        for (char c: s.toCharArray()) {
            count[c - 'a']++;
        }

        for (char c: t.toCharArray()) {
            count[c - 'a']--;
        }

        for (int i: count) {
            if (i != 0)
                return false;
        }

        return true;
    }
}

Optimal

To achieve the optimal solution O(m * n), where m is the number of strings and n is the length of longest string in the input, we encode each string as the count of their characters. 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap <String, List<String>> map = new HashMap<>();

        for(int i = 0; i < strs.length; i++) {
            int[] anagram = new int[26];
            for (int j = 0; j < strs[i].length(); j++) {
                anagram[strs[i].charAt(j) - 'a']++;
            }

            String decoded = Arrays.toString(anagram);
            if (map.containsKey(decoded)) {
                List<String> group = map.get(decoded);
                group.add(strs[i]);
            } else {
                ArrayList<String> group = new ArrayList<>();
                group.add(strs[i]);
                map.put(decoded, group);
            }
        }

        return new ArrayList(map.values());
    }
}