49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Thoughts

• Probably can reuse at least part of my solution to 242: Valid Anagram

  • I think there would be a way to use a HashMap as the key and a String list as the value

  • Use my solution for 242: Valid Anagram to gather keys on each word of the input, gradually adding them to the map, if the same character array exists, then add it to that list, otherwise its a new anagram

    • SO turns out you can't use primitive arrays as keys because, since they are primitives, they don't refer to the same information if they were non-primitive. Primitive arrays with the same values are actually distinct memory from each other instead of how non-primitive objects function in that objects of the same type and value point to the same physical location in memory

      • Because of this I had to figure out how to do some weird streaming stuff to convert the frequency array into a list

Solution

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<List<Integer>, ArrayList<String>> anas = new HashMap<List<Integer>, ArrayList<String>>();

        for (String s : strs) {
            // Calculate letter frequency
            int[] freq = new int[26];
            for (char i : s.toCharArray()) {
                freq[i - 97]++;
            }
            // Do some weird Stream stuff because int[]'s with the same values are not actually the same
            List<Integer> t = IntStream.of(freq).boxed().collect(Collectors.toList());

            // If the frequency table doesn't exist, create it, otherwise add to the existing table.
            if (!anas.containsKey(t)) {
                ArrayList<String> temp = new ArrayList<String>();
                temp.add(s);
                anas.put(t, temp);
            } else {
                ArrayList<String> temp = anas.get(t);
                temp.add(s);
                anas.put(t, temp);
            }
        }

        List<List<String>> ans = new ArrayList<List<String>>();
        for (ArrayList<String> a : anas.values()) {
            ans.add(a);
        }

        return ans;
    }
}

Time Complexity: O(n * k), where k is the average number of characters per string in the input
Space Complexity: O(n)

Conclusion

My solution was not fast, likely due in part to the weird streaming stuff I did to convert from an integer array to a List. I think there is definitely a better way to approach this problem considering that my solution is amount the slowest submissions. Overall not terrible for a problem though, it led to me reviewing some of the internal workings of Java as how it relates to arrays and primitives.