【一天一道LeetCode】#49. Group Anagrams

一天一道LeetCode系列

（一）題目

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],

Return:

[

[“ate”, “eat”,”tea”],

[“nat”,”tan”],

[“bat”]

]

Note:

1.For the return value, each inner list’s elements must follow the lexicographic order.

2.All inputs will be in lower-case.

（二）解題

本題的解法是通過sort對單個string中的字元進行排序，排序後如果相同的就放在一個vector

注意：題目中的Note部分有提到傳回的結果需要進行字典排序，一開始一直想不到辦法，後來在讨論區看到有人直接用sort對裡面的數進行排序就得出了字典排序，一下子恍然大悟！

class Solution {

public:

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

        vector<vector<string>> ret;

        map<string,int> nonrepstr;//用來存放排序後不重複的string

        int count = ;//用來辨別該string在ret中的位置

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

        {

            string tempstr = strs[i];

            sort(strs[i].begin(),strs[i].end(),less<char>());

            auto iter = nonrepstr.find(strs[i]);

            if(iter!=nonrepstr.end())//找到

            {

                (ret[iter->second]).push_back(tempstr);//如果找到了就放到ret裡相應的vector中

            }

            else//沒找到

            {

                nonrepstr.insert(pair<string, int>(strs[i],count++));//不重複的string放入map中

                vector<string> temp;

                temp.push_back(tempstr);

                ret.push_back(temp);//結果中也需要儲存一份

            }

        }

        for(int j=;j<count-;j++)//輸出結果要進行字典排序

        {

            sort(ret[j].begin(),ret[j].end());

        }

        return ret;

    }

};