Day10-字符串-同字符词语分组

BUPTrenyi

发布于 2019-07-15 16:54:21

4710

发布于 2019-07-15 16:54:21

文章被收录于专栏：算法其实很好玩算法其实很好玩

一今天唠唠嗑

三连冠王朝终于还是难再现了，KD早日康复，明年再来~当然了新王诞生，祝贺~

二上题！

Q:已知一组字符串，将所有anagram(由颠倒字母顺序而构成的字)放到一起输出。

例如:["eat", "tea", "tan", "ate", "nat", "bat"]

返回:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]

三冷静分析

首先要知道，输入是一个字符串数组，输出是一个二维字符串数组

那么随即问题来了：

如何建立哈希map，以及怎样设计key与value，就可以将各个字符相同的字符串，映射到一起？

我们要知道，c++标准STL中的vector，即字符串数组vector<string>，支持对每个字符串进行排序，比如“asdf”,排序后就是“adfs”

知道了这一点，是不是有思路了呢

那么，我们可以这样处理逻辑：

建立字符串到字符串数组的哈希map，遍历字符串数组strings中的每一个单词：

如果该单词排序后，从未出现在哈希map中：

设置从该单词到空字符串数组的映射

将该单词添加进哈希map[该单词]中

遍历完所有单词后，遍历哈希map，将value添加进字符串数组result中

即最后的哈希map是：

aet -> [“eat”, “tea”, “ate”]

ant -> [“tan”, “nat”]

abt -> [“bat”]

四完整代码及十分详细的注释

//
// Created by renyi on 2019-06-14.
//
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

vector<vector<string>> groupAnagram(vector<string>& strings){//这个函数，参数是字符串数组，返回类型是二位字符串数组
    map<string, vector<string>> anagram;//初始化一个哈希map，从字符串到字符串数组的映射
    vector<vector<string>> result;//存储最终的结果，即二位字符串数组

    for (int i = 0; i < strings.size(); i++) {//遍历strings里的每个单词
        string str = strings[i];//创建一个临时字符串变量str接收每个单词
        sort(str.begin(), str.end());//对单词进行排序

        if (anagram.find(str) == anagram.end()) {//如果排序后的单词str，不在哈希map里
            vector<string> temp;//创建一个空的字符串数组
            anagram[str] = temp;//以排序后的strings[i]作key
        }
        anagram[str].push_back(strings[i]);//在key对应的value中push当前单词
    }

    map<string, vector<string>> ::iterator it;//初始化一个指向，从字符串string，到字符串数组vector<string>的哈希map的指针it
    for (it = anagram.begin(); it != anagram.end(); it++) {
        result.push_back(it->second);//遍历哈希map：anagram，将其value，push进result
    }
    return result;
}

int main(){
    vector<string> strings;
    strings.emplace_back("nba");
    strings.emplace_back("dog");
    strings.emplace_back("god");
    strings.emplace_back("abn");
    strings.emplace_back("bna");
    strings.emplace_back("bat");
    
    vector<vector<string>> result = groupAnagram(strings);

    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%s]", result[i][j].c_str());
        }
        printf("\n");
    }
    return 0;
}

运行结果