Leetcode-49Group Anagrams

49. Group Anagrams

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.

题解：

输入一组字符串，将每个字符串中组成的字符完全相同的字符串分为一组，数组分组后的结果；

分析：

考虑到要将每个字符串中组成的字符相同的字符串分到一组，我们可以让哈希表的 key 存储字符的组成；考虑有26个字母，定义一个大小为26的整形数组并将数组中各元素初始化为0；对于字符串“ate”来说， 'a', 'e', 't' 各一个，则将 'a', 'e', 't' 的对应位置的元素改为1即可；同样，字符串中 'a' 有两个的话就把对应位置元素值改为2；这样，只要是相同组成的字符串，它对应的哈希表的key值一定相等，我们只需要让相同组成的字符串作为该key的value就可以了；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        map<vector<int>, vector<string>> hash_map;
        for (int i = 0; i < strs.size(); i++) {
            if (hash_map.find(getKey(strs[i])) != hash_map.end()) {
                hash_map[getKey(strs[i])].push_back(strs[i]);
            }
            else {
                vector<string> item;
                item.push_back(strs[i]);
                hash_map.insert(map<vector<int>, vector<string>>::value_type(getKey(strs[i]), item));
            }
        }
        map<vector<int>, vector<string>>::iterator it;
        vector<vector<string>> result;
        for (it = hash_map.begin(); it != hash_map.end(); it++) {
            result.push_back(it->second);
        }
        return result;
    }
private:
    vector<int> getKey(string str) {
        vector<int> key;
        for (int i = 0; i < 26; i++) {
            key.push_back(0);
        }
        for (int i = 0; i < str.length(); i++) {
            key[str[i] - 'a'] += 1;
        }
        return key;
    }
};

int main() {
    vector<string> strs;
    strs.push_back("eat");
    strs.push_back("tea");
    strs.push_back("ant");
    strs.push_back("ate");
    strs.push_back("nat");
    strs.push_back("bat");
    strs.push_back("eat");
    vector<vector<string>> result;
    Solution s;
    result = s.groupAnagrams(strs);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << ' ';
        }
        cout << endl;
    }
    //vector<int> result;
    //result = s.getKey("eat");
    //for (int i = 0; i < result.size(); i++) {
    //  printf("%d ", result[i]);
    //}
    return 0;
}

结果

ant nat
eat tea ate eat
bat

My Solution:

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        char_dict = {}
        for s in strs:
            if char_dict.get(''.join(sorted(s))):
                char_dict[''.join(sorted(s))].append(s)
            else:
                char_dict[''.join(sorted(s))] = [s]
        return list(char_dict.values())