Leetcode 49. Group Anagrams

I want to document my thought process on this Leetcode question, https://leetcode.com/problems/group-anagrams/description/.

First I'll try get an idea of what the function signature should be like while listening to the question. Then I'll start ask clarifying questions and come up with examples. After clarifying, I'll brainstorm some ideas to solve the problem. I want to try throwing different data structures at the problem for now, some may just be for the sake of considering them.

Function signature:

• List<List<String>> groupAnagrams(String[] strs)

Clarifying Questions / Assumptions:

• Input: null/empty? duplicates? sorted? charset?

• Output: How to handle null/empty? Return in any order?

• Assume: Only lowercase letters

Examples:

• strs = {"dad", "bad", "dab", "add"}

• strs = {"a", "b"}

• strs = null / {}

Brainstorm:

String length needs to be the same for it to be possible for 2 strings to be an anagram. (We might use this later on)

For each string in the list, I need to find out which group the string belongs to, and stick the string into its corresponding group's list, which holds the temp data while I work through the list.

If I had to solve this in real life with paper and pen, I would probably count the char frequency to determine the group.

(n = strs.length, m = length of longest string in strs array)

1. Store temp data into HashMap<String, List<String>> using char frequency as key

   • Use HashMap<String, List<String>> to store the anagram groups.
     For each string,
     Calculate its frequency int[],
     and convert the frequency to a String,
     using a separator between all frequency counts,
     to use as a key for the HashMap.
     (e.g. - key for "add" = "1,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0," )
     Add the string to the list under its key.
     Convert HashMap to List before returning.

   • time O(total_num_of_chars)
     space O(total_num_of_chars)

2. Store temp data into HashMap<String, List<String>> using sorted string as key

   • Same idea as above, except we sort the string to use as a key for the HashMap.
     (e.g. - key for "dad" = "add" )

   • time O(n * mlogm) ~ O(n * m^2) // for quicksort
     space O(n * logm) ~ O(n * m) // for quicksort

3. Store temp data into HashMap<String, Trie> using char frequency as key

   • Theoretically speaking, if the strs array is large enough and has enough overlaps, we could probably consider using a trie? Time/Space complexity should be the same, insert will only go through each char once, and when we want to return the result, we would go through each char once, but it would be a hassle to implement.

   • time O(total_num_of_chars)
     space O(total_num_of_chars)

Code:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return Collections.emptyList();

        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            String key = toKey(s);
            map.putIfAbsent(key, new ArrayList<String>());
            map.get(key).add(s);
        }        
        return new ArrayList<List<String>>(map.values());
    }

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count.length; i++) {
            sb.append(count[i]).append(",");
        }
        return sb.toString();
    }
}

Let me know if there is anything I should have considered, or has an error! I'm happy to get any feedback.