# [LeetCode 49. Group Anagrams ](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/614/week-2-august-8th-august-14th/3887/)
### Daily challenge Aug 12, 2021 (MEDIAN)

>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.

:::info
**Example 1:**
**Input:** strs = ["eat","tea","tan","ate","nat","bat"]
**Output:** [["bat"],["nat","tan"],["ate","eat","tea"]]
:::

:::info
**Example 2:**
**Input:** strs = [""]
**Output:** [[""]]
:::

:::info
**Example 3:**
**Input:** strs = ["a"]
**Output:** [["a"]]
:::

:::warning
**Constraints:**
* 1 <= strs.length <= 104
* 0 <= strs[i].length <= 100
* strs[i] consists of lower-case English letters.
:::

---

### Approach 1 : Sort :bulb:
**`524 ms ( % )`** **`O()`**

* **`vector<string> list`** 紀錄每個 `group` 的字串。
* 將 `strs[i]` 進行 `sort`，再去和 `list` 比對。
---> 如果相同，就表示是相同 `group`。
---> 不同，新增一個 `gorup`。
* 最後根據比對結果存入 **`ans`**。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        vector<string> list;
        int size = strs.size();
        
        vector<string> temp = strs;
        for(int i=0; i<size; i++){
            sort(temp[i].begin(), temp[i].end());
        }
        
        for(int i=0; i<size; i++){
            bool flag = false;
            for(int j=0; j<list.size(); j++){
                if(temp[i] == list[j]){
                    ans[j].push_back(strs[i]);
                    flag = true;
                    break;
                }
            }
            if(!flag){
                ans.push_back(vector<string>(1, strs[i]));
                list.push_back(temp[i]);
            }   
        }
        
        return ans;
    }
};

### Approach 2 : Map + Sort :book:
**`28 ms ( 89.97% )`** **`O()`**

* 概念與 `Approach 1` 相同，但是直接使用 **`map`** 代替原本的 **`vector`**，效率較高。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, vector<string>> list;
        
        for(auto c : strs){
            string original = c;
            sort(c.begin(), c.end());
            
            list[c].push_back(original);
        }
        
        for(auto key : list){
            ans.push_back(key.second);
        }
        
        return ans;
    }
};