Group Anagrams

• Lintcode : 772 / Leetcode : 49
• Level : Medium

Problem

Given an array of strings, group anagrams together.

Example
Example 1:

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

Input:
["eat","nowhere"]
Output:
[["eat"],
 ["nowhere"]]
Notice
All inputs will be in lower-case.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    /**
     * @param strs: the given array of strings
     * @return: The anagrams which have been divided into groups
     */
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> hash;
        for (auto i : strs) {
            string s = i;
            sort(s.begin(), s.end());
            hash[s].push_back(i);
        }
        vector<vector<string>> ans;
        for (auto it = hash.begin(); it != hash.end(); it++) {
            ans.push_back(it -> second);
        }
        return ans;
    }
};

tags: other

​