Group Anagrams

佚名 6年前 (2019-05-11) 随笔 991人围观抢沙发百度已收录

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

All inputs will be in lowercase.
The order of your output does not matter.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
//lexicographical_compare
using namespace std;

class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        vector<vector<string>> res;
        if(strs.empty())
            return res;
        if(strs.size()==1)
        {
            res.push_back(strs);
            return res;
        }

        res.resize(strs.size());
        unordered_map<string,int> mp;
        int row=0;
        for(int i=0;i<strs.size();++i)
        {
            string tmp=strs.at(i);
            sort(tmp.begin(),tmp.end());
            if(mp.find(tmp)!=mp.end())
            {
                res[mp[tmp]].push_back(strs.at(i));
            }
            else
            {
                res.at(row).push_back(strs.at(i));
                mp.insert({tmp,row});
                ++row;
            }
        }
        res.resize(row);
        return res;
    }
};

int main()
{
    Solution s;
    vector<string> arr{"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> res(s.groupAnagrams(arr));
    for(auto i:res)
    {
        for(auto j:i)
            cout<<j<<" ";
        cout<<endl;
    }
    return 0;
}