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

2024-05-28 00:36

本文主要是介绍力扣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. 创建 mpmp = {}(初始状态)

  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删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

Python办公自动化实战之打造智能邮件发送工具

《Python办公自动化实战之打造智能邮件发送工具》在数字化办公场景中,邮件自动化是提升工作效率的关键技能,本文将演示如何使用Python的smtplib和email库构建一个支持图文混排,多附件,多... 目录前言一、基础配置:搭建邮件发送框架1.1 邮箱服务准备1.2 核心库导入1.3 基础发送函数二、

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Python包管理工具pip的升级指南

《Python包管理工具pip的升级指南》本文全面探讨Python包管理工具pip的升级策略,从基础升级方法到高级技巧,涵盖不同操作系统环境下的最佳实践,我们将深入分析pip的工作原理,介绍多种升级方... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert