49.Group Anagrams同字符词语分组

qlmx
qlmx
qlmx
50
文章
2
评论
2020年2月15日00:03:58 评论 889阅读4分55秒

49.Group Anagrams同字符词语分组

1 描述

Given an array of strings, group anagrams together.

Example:

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

2 思路

  1. 建立hash表,依次取数组中的值存入瞬时变量,然后对变量进行排序,最后将排序后的结果作为key值,原始结果作为value,最后将同一个key值得元素全部取出。

  2. 方法2对方法一中的key值做出了调整,采用26个字符转为key,具体如下

    ​ [a, b, c, d, e, …., t,…,z]

    编码:[1, 0, 0, 0, 1,…, 1,…,0] => eat, tea, ate

    ​ [a, b, c, ..., n, …., t,…,z]

    编码:[1, 0, 0,…, 1,…, 1,…,0] => tan, nat

3 C++

  • 方法一
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        map<string, vector<string>> anagram;

        for(int i=0; i<strs.size(); i++) {
            string str = strs[i];
            sort(str.begin(), str.end());

            if(anagram.find(str) == anagram.end()) {
                vector<string> item;
                anagram[str] = item;
            }
            anagram[str].push_back(strs[i]);
        }

        map<string, vector<string>>::iterator it;
        for(it = anagram.begin(); it != anagram.end(); it++) {
            result.push_back((*it).second);
        }
        return result;
    }
};
  • 方法二
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        map<vector<int>, vector<string>> anagram;

        for(int i=0; i<strs.size(); i++) {
            vector<int> vec;
            str_to_vector(strs[i], vec);

            if(anagram.find(vec) == anagram.end()) {
                vector<string> item;
                anagram[vec] = item;
            }
            anagram[vec].push_back(strs[i]);
        }

        map<vector<int>, vector<string>>::iterator it;
        for(it = anagram.begin(); it != anagram.end(); it++) {
            result.push_back((*it).second);
        }
        return result;
    }
private:
    void str_to_vector(string &str, vector<int> & vec) {
        for(int i=0; i<26; i++) {
            vec.push_back(0);
        }

        for(int i=0; i<str.length(); i++) {
            vec[str[i] - 'a'] ++;
        }
    }
};
继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年2月15日00:03:58
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: