<Data Structures/Algorithms> LeetCode - 49. Group Anagrams

LeetCode 49. Group Anagrams

Problem Link

A straightforward approach is to sort each string. Different anagrams will become identical after sorting, so we can use the sorted string as a key in a map. When inserting into the map:

• If the key does not exist, create a new group and record its position.
• If the key exists, append the current string to the corresponding group in the result.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        map<string, int> posMap;
        int pos = 0; // Next group index
        for(auto& str : strs){
            string cur = str;
            sort(cur.begin(), cur.end());
            if(posMap.find(cur) == posMap.end()){
                posMap.emplace(cur, pos);
                vector<string> anagramList;
                anagramList.push_back(str);
                ans.push_back(anagramList);
                pos++;
            } else{
                int curPos = posMap.find(cur)->second;
                ans[curPos].push_back(str);
            }
        }
        return ans;
    }
};

中文原文

[LeetCode hot 100] 49. 字母异位词分组

题目链接

这道题比较直觉的做法就是先对每个词排序，因为不同异位词按照字母排序之后的异位词就是统一的了，因此将这个排序后的词作为map的键，查找map时如果存在这个键，就按照map中记录的位置去找这个键对应的异位词分组在返回结果中的位置，并且在这个异位词分组后面加上当前字符串。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        map<string, int> posMap;
        int pos = 0;//分组的下一个下标
        for(auto& str : strs){
            string cur = str;
            sort(cur.begin(), cur.end());
            if(posMap.find(cur) == posMap.end()){
                posMap.emplace(cur, pos);
                vector<string> anagramList;
                anagramList.push_back(str);
                ans.push_back(anagramList);
                pos++;
            } else{
                int curPos = posMap.find(cur)->second;
                ans[curPos].push_back(str);
            }
        }
        return ans;
    }
};