【LeetCode】 49. Group Anagrams

Description

Given an array of strings, group anagrams together.

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

給予一個字串的陣列，將同樣的字謎組合組在一起。
(所謂的同樣的字謎指每個字串內含的字母完全一樣，連數量都一樣，只是排列組合不同)
注意：
所有輸入都是小寫字母。
你輸出結果的先後順序並不重要。

Example:

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

Solution

• 將所有字串先排序，如果同樣字謎就會變得一模一樣。
• 這邊使用map處理，使用排列完之後的結果作為key，content為原始字串。
• 最後要把map轉換回去，因為題目規定要回傳vector。
  • 在這邊使用auto語法，為新版C++的用法，概念和python, C#的很像。

Code

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> strs_sort(strs);
        map<string, vector<string>> map_ans;
        vector<vector<string>> ans;
        for(int i = 0; i < strs.size(); i++)
            sort(strs_sort[i].begin(), strs_sort[i].end());
        for(int i = 0; i < strs.size(); i++)
        {
            if(map_ans.find(strs_sort[i]) == map_ans.end())
                map_ans[strs_sort[i]] = vector<string>();
            map_ans[strs_sort[i]].push_back(strs[i]);
        }
        for(auto it : map_ans)
            ans.push_back(it.second);
        return ans;
    }
};

tags: LeetCode C++