Leetcode sword finger offer II 033 Modified phrase

link

The finger of the sword Offer II 033. Morpheme phrase

subject

Given an array of strings  strs , take   A modifier   Put together . You can return a list of results in any order .

Be careful ： If each character in two strings appears the same number of times , They are called mutuals .

Example

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 <= 10e4
• 0 <= strs[i].length <= 100
• strs[i]  Only lowercase letters

Ideas

Anagrams are two words with the same number of letters , therefore , If you sort the letters of two anagrams , The final two words must be equal .

therefore , We can use the sorted words of each word as the index of the hash table , The original word is stored in the string array corresponding to the index , Finally, all arrays in the hash table can be stored in the result array .

C++ Code

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        vector<vector<string>> ans;
        for(auto s:strs)
        {
            string tmp=s; //tmp Yes s Sorted string  s For the original string 
            sort(tmp.begin(),tmp.end());
            map[tmp].push_back(s); // After sorting tmp The original string of the same string s Save to hash table 
        }
        for(auto &[x,y]: map) ans.push_back(y); // Store the string array stored in the hash table one by one ans
        return ans;
    }
};