[leetcode]Group Anagrams

Problem

Given an array of strings, group anagrams together.

Example:

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

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

Note:

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

Solution

题目的意思是将所有字谜分组保存。所谓字谜anagram, 就是两个词所用的字母及其个数都是一样的，但字母的位置不一样。比如 abcd和cbda 就是 anagram.

了解题意之后，着手解决问题。首先，判断两个字符串是否是字谜，可以将两个字符串排序，比较排序后的结果是否相等，判断是否是字谜。之后的问题，就是分组保存，我们用字典形式保存，这样保证所有字谜都存在相应字谜对应的列表中。字典的键可以用字符串排序后的结果，值就是对应分组保存的列表。具体代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        if (strs.empty()) return res;
        
        unordered_map<string, vector<string>> mapping;
        for (auto str : strs){
            string t = str;
            sort(t.begin(), t.end());//排序结果作为键
            mapping[t].push_back(str);//保存到对应的列表中
        }
        //store in the res
        for (auto k: mapping)
            res.push_back(k.second);
        
        return res;
    }

};

推荐文章（由hexo文章推荐插件驱动）

• leetcode-含有重复字符的最长子串