49. Group Anagrams

Question

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.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Algorithm

For this question, you need to know what is an anagram.

Then to get the result list of list, you need to check if each string is an anagram of a pattern or template.

If a str is not in the map key set, we regard it as a new anagram and add it to the map otherwise we find it anagram in the map keys, we put it into that group list.

Now the question becomes how do we define a pattern/template. We can sort the characters or we can count the characters, the key here is to define a standard. Anagrams strings will be transformed to the same template.

Code

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String key = helper(str);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(str);
        }
        
        List<List<String>> res = new ArrayList<>();
        for (List<String> list : map.values()) {
            res.add(new ArrayList<>(list));
        }
        return res;
    }
    
    private String helper(String str) {
        int[] count = new int[26];
        for (Character ch : str.toCharArray()) {
            count[ch - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                sb.append(String.valueOf(count[i]) + String.valueOf(i + 'a'));
            }
        }
        return sb.toString();
    }
}