【leetcode】49. Group Anagrams 字母组合相同的单词聚合

1. 题目

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.

2. 思路

对每一个字符串a，对齐排序得到b，建立一个<b,a>的映射，对所有key相同的多个a合并起来即可。实现时用<sort_string,vector<string_raw>>来完成。

3. 代码

耗时：75ms

class Solution {
public:
    // 将string的排序结果作为key,建立<k,list>结果
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        for (int i = 0; i < strs.size(); i++) {
            string s_dup = strs[i];
            sort(s_dup.begin(),s_dup.end());
            auto it = map.find(s_dup);
            if (it == map.end()) {
                vector<string> first;
                first.push_back(strs[i]);
                map[s_dup] = first;
            } else {
                it->second.push_back(strs[i]);
            }
        }
        vector<vector<string>> ret;
        for (auto it = map.begin(); it != map.end(); it++) {
            ret.push_back(it->second);
        }
        return ret;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!