Leetcode Study Day 21

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.

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.

My solution

I found one solution to solve “Anagrams” problems, which is to sort the string. If the sorted result for two strings are the same, then they are anagrams.

Based on this idea, I sort each string and put the sorted result as the keys of the map. The values of the map are the original strings. Then I loop through the map and put the values into the result vector.

Two things I learnt today:

1. How to create a map:

   map <string, vector<string>> strOrder;

2. How to loop through a map and select the values (select key is pair.first):

   for (const auto &pair: strOrder){
       ans.push_back(pair.second);
   }

   Full code

   class Solution {
   public:
       vector<vector<string>> groupAnagrams(vector<string>& strs) {
           map <string, vector<string>> strOrder;
           for (int i = 0; i < strs.size(); i++){
               string str_copy(strs[i]); 
               sort(str_copy.begin(), str_copy.end());
               strOrder[str_copy].push_back(strs[i]);
           }
   
           vector <vector<string>> ans;
           for (const auto &pair: strOrder){
               ans.push_back(pair.second);
           }
           return ans;
       }
   };