力扣hot 100：49. 字母异位词分组(python C++)

2024-05-28 00:36
文章标签 python c++ 分组 力扣 100 字母 hot 49 异位

本文主要是介绍力扣hot 100：49. 字母异位词分组(python C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 题目描述：
    • 题解（python）：（方法一：排序）
      • 代码解析
      • 代码运行解析
    • 题解（C++）：（方法一：排序）
      • 代码解析&运行解析

原题目链接

题目描述：

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

题解（python）：（方法一：排序）

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:key = "".join(sorted(st))mp[key].append(st)return list(mp.values())

代码解析

这段代码定义了一个名为 Solution 的类，类中包含一个名为 groupAnagrams 的方法。该方法用于将一组字符串按字母异位词（anagram）分组。以下是代码的逐行解析：

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  • 这段代码定义了一个类 Solution，类中包含一个方法 groupAnagrams。这个方法接收一个参数 strs，它是一个字符串列表（List[str]），返回值是一个列表，列表中的每个元素也是一个字符串列表（List[List[str]]）。
        mp = collections.defaultdict(list)
  • 这里定义了一个名为 mp 的变量，它是一个 defaultdict（来自 collections 模块）。defaultdict 是一种字典，它在引用的键不存在时会自动创建键，并将其值初始化为指定的默认值。在这个例子中，默认值是一个空列表。
        for st in strs:key = "".join(sorted(st))mp[key].append(st)
  • 这一段代码遍历输入的字符串列表 strs。
    • 对于每个字符串 st，通过 sorted(st) 对字符串的字符进行排序，得到一个排序后的字符列表。
    • 然后通过 ''.join(sorted(st)) 将排序后的字符列表重新组合成一个字符串 key。
    • 使用这个 key 作为键，将原始字符串 st 添加到 mp 字典中对应的列表中。
        return list(mp.values())
  • 最后，将字典 mp 中所有的值（即各个字母异位词分组的列表）转换为一个列表，并返回这个列表。

总结：

  • 这个方法的主要作用是将输入的字符串列表按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
  • 通过对每个字符串的字符进行排序，可以生成唯一的键（排序后的字符串），用这个键来将原始字符串分组。

例如，输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

代码运行解析

当然可以！我们来详细跟踪代码执行的每一步，以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

import collectionsclass Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)
  • 创建了一个 defaultdict，初始状态 mp 是空的：mp = {}。
        for st in strs:key = "".join(sorted(st))mp[key].append(st)

遍历 strs 列表，并对每个字符串执行以下操作：

  1. 处理 st = "eat":

    • sorted("eat") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("eat")，更新后的 mp 是：{'aet': ['eat']}

  2. 处理 st = "tea":

    • sorted("tea") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("tea")，更新后的 mp 是：{'aet': ['eat', 'tea']}

  3. 处理 st = "tan":

    • sorted("tan") 结果是 ['a', 'n', 't']
    • key = "".join(['a', 'n', 't']) 结果是 "ant"
    • mp["ant"].append("tan")，更新后的 mp 是：{'aet': ['eat', 'tea'], 'ant': ['tan']}

  4. 处理 st = "ate":

    • sorted("ate") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("ate")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}

  5. 处理 st = "nat":

    • sorted("nat") 结果是 ['a', 'n', 't']
    • key = "".join(['a', 'n', 't']) 结果是 "ant"
    • mp["ant"].append("nat")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}

  6. 处理 st = "bat":

    • sorted("bat") 结果是 ['a', 'b', 't']
    • key = "".join(['a', 'b', 't']) 结果是 "abt"
    • mp["abt"].append("bat")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
        return list(mp.values())
  • 最终，将 mp 的值转换为列表：list(mp.values())。
  • 返回结果是 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

综上，代码的每一步执行结果如下：

  1. mp = {} （初始状态）
  2. mp = {'aet': ['eat']}
  3. mp = {'aet': ['eat', 'tea']}
  4. mp = {'aet': ['eat', 'tea'], 'ant': ['tan']}
  5. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
  6. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
  7. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
  8. 返回值：[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

题解（C++）：（方法一：排序）

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;for (string& str:strs){string key = str;sort(key.begin(),key.end());mp[key].emplace_back(str);}vector<vector<string>> ans;for (auto it = mp.begin();it != mp.end(); ++ it){ans.emplace_back(it->second);}return ans;}
};

代码解析&运行解析

这段代码定义了一个名为 Solution 的类，类中包含一个名为 groupAnagrams 的方法。这个方法用于将一组字符串按字母异位词（anagram）分组。以下是代码的逐行解析：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {
  • 这段代码定义了一个类 Solution，类中包含一个公有方法 groupAnagrams。该方法接收一个引用参数 strs，它是一个字符串的向量（vector<string>），返回值是一个二维字符串向量（vector<vector<string>>）。
        unordered_map<string, vector<string>> mp;
  • 这里定义了一个名为 mp 的变量，它是一个 unordered_map，键类型是 string，值类型是 vector<string>。这个哈希映射用于将排序后的字符串（作为键）映射到原始字符串列表（作为值）。
        for (string& str: strs) {string key = str;sort(key.begin(), key.end());mp[key].emplace_back(str);}
  • 这一段代码遍历输入的字符串向量 strs。
    • 对于每个字符串 str，将其复制到 key 中。
    • 通过 sort(key.begin(), key.end()) 对 key 中的字符进行排序。
    • 使用排序后的 key 作为键，将原始字符串 str 添加到 mp 字典中对应的列表中。
        vector<vector<string>> ans;
  • 创建一个空的二维字符串向量 ans，用于存储结果。
        for (auto it = mp.begin(); it != mp.end(); ++it) {ans.emplace_back(it->second);}
  • 遍历 mp 中的每一个键值对。
    • 对于每一个键值对，将值（即一个字符串列表）添加到 ans 中。
        return ans;}
};
  • 最后，返回 ans，它包含了按字母异位词分组的字符串列表。

总结：

  • 这个方法的主要作用是将输入的字符串向量按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
  • 通过对每个字符串的字符进行排序，可以生成唯一的键（排序后的字符串），用这个键来将原始字符串分组。

例如，输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

让我们详细跟踪代码执行的每一步，以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

假设输入是 ["eat", "tea", "tan", "ate", "nat", "bat"]，代码的每一步执行结果如下：

  1. 创建 mp：mp = {}（初始状态）

  2. 处理 str = "eat"：

    • key = "eat"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("eat")，更新后的 mp 是：{"aet": ["eat"]}

  3. 处理 str = "tea"：

    • key = "tea"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("tea")，更新后的 mp 是：{"aet": ["eat", "tea"]}

  4. 处理 str = "tan"：

    • key = "tan"
    • sort(key.begin(), key.end()) 结果是 key = "ant"
    • mp["ant"].emplace_back("tan")，更新后的 mp 是：{"aet": ["eat", "tea"], "ant": ["tan"]}

  5. 处理 str = "ate"：

    • key = "ate"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("ate")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

  6. 处理 str = "nat"：

    • key = "nat"
    • sort(key.begin(), key.end()) 结果是 key = "ant"
    • mp["ant"].emplace_back("nat")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

  7. 处理 str = "bat"：

    • key = "bat"
    • sort(key.begin(), key.end()) 结果是 key = "abt"
    • mp["abt"].emplace_back("bat")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

遍历 mp，将每个值（字符串列表）添加到 ans 中：

  • ans = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

返回 ans，最终结果是：[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

这篇关于力扣hot 100：49. 字母异位词分组(python C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1009040。

相关文章

Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
Python正则表达式匹配和替换的操作指南

Python正则表达式匹配和替换的操作指南

《Python正则表达式匹配和替换的操作指南》正则表达式是处理文本的强大工具,Python通过re模块提供了完整的正则表达式功能,本文将通过代码示例详细介绍Python中的正则匹配和替换操作,需要的朋... 目录基础语法导入re模块基本元字符常用匹配方法1. re.match() - 从字符串开头匹配2.
阅读更多...
C++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
通过Docker容器部署Python环境的全流程

通过Docker容器部署Python环境的全流程

《通过Docker容器部署Python环境的全流程》在现代化开发流程中,Docker因其轻量化、环境隔离和跨平台一致性的特性,已成为部署Python应用的标准工具,本文将详细演示如何通过Docker容... 目录引言一、docker与python的协同优势二、核心步骤详解三、进阶配置技巧四、生产环境最佳实践
阅读更多...
Python一次性将指定版本所有包上传PyPI镜像解决方案

Python一次性将指定版本所有包上传PyPI镜像解决方案

《Python一次性将指定版本所有包上传PyPI镜像解决方案》本文主要介绍了一个安全、完整、可离线部署的解决方案,用于一次性准备指定Python版本的所有包,然后导出到内网环境,感兴趣的小伙伴可以跟随... 目录为什么需要这个方案完整解决方案1. 项目目录结构2. 创建智能下载脚本3. 创建包清单生成脚本4
阅读更多...
Python实现Excel批量样式修改器(附完整代码)

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函
阅读更多...
python获取指定名字的程序的文件路径的两种方法

python获取指定名字的程序的文件路径的两种方法

《python获取指定名字的程序的文件路径的两种方法》本文主要介绍了python获取指定名字的程序的文件路径的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 最近在做项目，需要用到给定一个程序名字就可以自动获取到这个程序在Windows系统下的绝对路径，以下
阅读更多...
使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解

使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解

《使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解》本文详细介绍了如何使用Python通过ncmdump工具批量将.ncm音频转换为.mp3的步骤,包括安装、配置ffmpeg环... 目录1. 前言2. 安装 ncmdump3. 实现 .ncm 转 .mp34. 执行过程5. 执行结
阅读更多...
Python实现批量CSV转Excel的高性能处理方案

Python实现批量CSV转Excel的高性能处理方案

《Python实现批量CSV转Excel的高性能处理方案》在日常办公中,我们经常需要将CSV格式的数据转换为Excel文件,本文将介绍一个基于Python的高性能解决方案,感兴趣的小伙伴可以跟随小编一... 目录一、场景需求二、技术方案三、核心代码四、批量处理方案五、性能优化六、使用示例完整代码七、小结一、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2