49. Group Anagrams

49. Group Anagrams  ( https://leetcode.com/problems/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.

思路：
要先把每一個字串都排序過，例如 eat -> aet
然後把排序過的字串，在做一次排序，例如
 ["eat","tea","tan","ate","nat","bat"] ->  ["abt","aet","aet","aet","ant","ant"]
而且排序後的字串要記住排序前的字串
排序後|排序前
abt | bat
aet | ate
aet | eat
aet | tea
ant | nat
ant | tan

所以要用 pair，first 放排序後的，second 放排序前的
first 排好了，sencond 就跟著變
把 pair 丟進去 vector 排序
string 的排序在C++，預設都會排的棒棒，不用自己寫比較函式

解答：

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        vector<string> sortedStrs(strs);

        vector<pair<string, string>> pairStrs;

        for(int i = 0; i < sortedStrs.size(); i++)

        {

            sort(sortedStrs[i].begin(), sortedStrs[i].end());

            pair<string, string> p(sortedStrs[i], strs[i]);

            pairStrs.push_back(p);

        }

        sort(pairStrs.begin(), pairStrs.end());

        for(vector<pair<string, string>>::iterator i = pairStrs.begin(); i != pairStrs.end(); i++)

        {

            cout << i->first << " | " << i->second << endl;

        }

        vector<string> initGroup;

        initGroup.push_back(pairStrs[0].second);

        vector<vector<string>> result;

        result.push_back(initGroup);

        for(int i = 1; i < strs.size(); i++)

        {

            if (pairStrs[i].first == pairStrs[i-1].first)

            {

                result[result.size()-1].push_back(pairStrs[i].second);

            } else {

                vector<string> newGroup;

                newGroup.push_back(pairStrs[i].second);

                result.push_back(newGroup);

            }

        }

        return result;

    }

};

參考：https://www.youtube.com/watch?v=1zU77mcQJ-U&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=6