LeetCode49 Group Anagrams

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: All inputs will be in lower-case. （Medium）

分析：

一个简单的思路，就是把每个string赋上其在数组中的位置组成一个结果（保留位置信息）。

然后对每个string排序，再对所有string以字典序排序使得一样的string相邻。

最后走一遍循环，把一样的string对应的原vector中的string添加到结果中即可。

代码：

 class Solution {

 struct node{

     string str;

     int num;

     node(string s, int n):str(s),num(n){}

     bool operator< (const node& n2) const{

         return str < n2.str;

     }

 };

 public:

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

         vector<node> v;

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

             v.push_back(node(strs[i],i));

         }

         for (int i = ; i < v.size(); ++i) {

             sort(v[i].str.begin(), v[i].str.end());

         }

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

         vector<vector<string>> result;

         vector<string> temp;

         temp.push_back(strs[v[].num]);

         for (int i = ; i < v.size(); ++i) {

             if (v[i].str == v[i - ].str) {

                 temp.push_back(strs[v[i].num]);

             }

             else {

                 result.push_back(temp);

                 temp.clear();

                 temp.push_back(strs[v[i].num]);

             }

         }

         result.push_back(temp);

         return result;

     }

 };

巴特西

LeetCode49 Group Anagrams

最新文章

热门文章