1. Title requirements

• You will be given an array of strings, which you can return in any order by combining heterographic words.
• Alphabetic words are new words that result from rearranging the letters of the source word, and the letters in all source words are usually used 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"]]

• Tips:
• • 1 <= strs.length <= 104；
• • 0 <= strs[i].length <= 100；
• • strs[i] contains only lowercase letters.

2. Solving ideas

• Two strings are heterographic words for each other if and only if they contain the same letter. Strings in the same set of hetero-alphabetic words have the same points. You can use the same points as the flags for a set of hetero-alphabetic words, use a hash table to store each set of hetero-alphabetic words, use the hash table keys as the flags for a set of hetero-alphabetic words, and use the hash table values as a list of hetero-alphabetic words.
• Traverse through each string, and for each string, get the flags of the set of alphabetic words in which the string is located, and add the current string to the list of alphabetic words in that set. After traversing all strings, each key-value pair in the hash table is a set of alphabetic words.

3. Solving algorithm

1 Sort

• Since two strings of heterographic words contain the same letters, the resulting strings after sorting the two strings separately must be the same, so the sorted string can be used as the key of the hash table.
• Java example:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

• C++ example:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

(2) Count

• Since two strings of heterographic words contain the same letters, the number of occurrences of the same letter in both strings must be the same, so the number of occurrences of each letter can be represented as a string as the key of the hash table.
• Since strings contain only lowercase letters, for each string, an array of 26 lengths can be used to record the number of occurrences of each letter. It is important to note that when using arrays as keys to a hash table, support varies from language to language, so implementation varies from language to language.
• Java example:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // Each occurrence greater than 0 letters and occurrences are concatenated sequentially into strings as keys to the hash table
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

• C++ example:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // Customize hash functions for array < int, 26 > types
        auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string& str: strs) {
            array<int, 26> counts{};
            int length = str.length();
            for (int i = 0; i < length; ++i) {
                counts[str[i] - 'a'] ++;
            }
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};