您好,欢迎来到好走旅游网。
搜索
您的当前位置:首页LeetCode: 49. Group Anagrams 对颠倒字符串分组

LeetCode: 49. Group Anagrams 对颠倒字符串分组

来源:好走旅游网

Leetcode: 49. Group Anagrams 对颠倒字符串分组

问题描述

Given an array of strings, group anagrams together.

Example:,
Given:

Return:

[
[“ate”, “eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]

Note: All inputs will be in lower-case.

Anagrams即字母顺序颠倒的字符串,例如"abc","acb"和"bca"是anagrams,"abc"和"acd"就不是。
传送门:
相关题目:和

解决方案

两级map结构,对每一个字符串用低级map来统计每个字母出现的个数,在到高级map中查询是否出现过同一anagram的字符串,如果有则插入到输出向量的指定位置,没有则插入到输出向量的尾部。
本方法的特点在于用string类型替代了数组来统计每个字母出现的个数。

运行时间29ms,超过93.45%

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        //输入空则输出空
        if(strs.empty())    return result;
        //不能用<vector<int>,int>,因为vector<int>不能用<符号来比较
        unordered_map<string,int> map;
        int count = 0;
        for(string str:strs){
            string m(26,0);//string可以看成是一个数组
            for(char ch:str){
                m[ch-'a']++;
            }
            if(map.find(m) == map.end()){
	            //map中没找到则将字符串str插入result尾部,更新map,count
                map.insert(pair<string,int>(m,count));
                count++;
                vector<string> rs;
                rs.push_back(str);
                result.push_back(rs);
            }
            else{
	            //字符串str的anagram已经出现过,则将str插入result相应位置
                result[map[m]].push_back(str);
            }
        }
        return result;
    }
};

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- haog.cn 版权所有 赣ICP备2024042798号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务