专栏首页算法其实很好玩Day10-字符串-同字符词语分组

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

一 今天唠唠嗑

三连冠王朝终于还是难再现了,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;
}

运行结果

五 总结一下

大家应该注意到了,只要理顺逻辑,建立了正确的哈希map,注意临界点与特殊边界,字符串的初级算法问题思路并不是很难的

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day12-字符串-重复的DNA序列

    Q:将DNA序列看作是只包含【'A', 'C', 'G', 'T'】4个字符的字符串。现有一个这样的字符串,找到所有长度为10且出现次数超过1的子串。

    BUPTrenyi
  • 递归&回溯-子集之和

    Q:已知一个数组,可能有重复元素,给定值target,求出所有子集中,和为target的,不重复的子集。

    BUPTrenyi
  • Day9-字符串-字符模式匹配

    Q:已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符串str中的单词与pattern中的字符一一...

    BUPTrenyi
  • LeetCode-49-Group-Anagrams

    输入一个字符串数组,输出的是:将相同字符的字符串放在一个数组的二维数组。相同字符的处理,基本就是要对字符串排序的。然后需要考虑的就是排序好的那一个字符串怎么存的...

    小二三不乌
  • 关于C#委托的一些学习笔记

    1.什么是委托就是把方法作为参数传给另一个方法。委托说指向的函数,必须和函数具有相同的签名(返回值和参数类型) Public delegate void D...

    码农阿宇
  • Leetcode 49. Group Anagrams

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • IDA7.0 配置内核调试,双机调试

    记住是路径.而不是windbg.exe. 原因是 IDA需要依靠 windbg目录下的. Dbgeng.dll来进行调试

    IBinary
  • 【LeetCode程序员面试金典】面试题 01.06. Compress String LCCI

    Implement a method to perform basic string compression using the counts of repea...

    韩旭051
  • 基于GitLab的Code Review教程

    也就是说,使用GitLab进行Code Review就是在分支合并环节发起Merge Request,然后Code Review完成后将代码合并到目标分支。

    KenTalk
  • 3个机器学习算法

      根据一些 feature 进行分类,每个节点提一个问题,通过判断,将数据分为两类,再继续提问。这些问题是根据已有数据学习出来的,再投入新数据的时候,就可...

    陆勤_数据人网

扫码关注云+社区

领取腾讯云代金券