当前位置: 首页> 健康> 美食 > 长春大学_关于三亚的网页设计_软文营销的技巧有哪些_网站如何优化排名软件

长春大学_关于三亚的网页设计_软文营销的技巧有哪些_网站如何优化排名软件

时间:2025/7/11 22:30:16来源:https://blog.csdn.net/m0_63951116/article/details/145783692 浏览次数:0次
长春大学_关于三亚的网页设计_软文营销的技巧有哪些_网站如何优化排名软件

LeetCode 热题 100 | 49. 字母异位词分组

大家好,今天我们来解决一道经典的算法题——字母异位词分组。这道题在LeetCode上被标记为中等难度,要求我们将字母异位词组合在一起。下面我将详细讲解解题思路,并附上Python代码实现。


问题描述

给定一个字符串数组 strs,将其中所有字母异位词组合在一起。字母异位词是指由相同字母重新排列形成的单词。

示例:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解题思路

核心思想
  1. 哈希表分组

    • 使用哈希表(字典)来存储字母异位词的分组结果。
    • 将每个字符串排序后的结果作为哈希表的键,原始字符串作为值。
  2. 排序作为键

    • 由于字母异位词排序后的结果相同,可以将排序后的字符串作为哈希表的键。
  3. 返回结果

    • 遍历哈希表的值,将分组结果存入列表并返回。

Python代码实现

def groupAnagrams(strs):from collections import defaultdict# 使用 defaultdict 初始化哈希表anagrams = defaultdict(list)# 遍历字符串数组for s in strs:# 将字符串排序后作为键sorted_s = ''.join(sorted(s))# 将原始字符串添加到对应的分组中anagrams[sorted_s].append(s)# 返回分组结果return list(anagrams.values())# 测试示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]print(groupAnagrams(strs1))  # 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams(strs2))  # 输出: [[""]]
print(groupAnagrams(strs3))  # 输出: [["a"]]

代码解析

  1. 哈希表初始化

    • 使用 defaultdict(list) 创建一个哈希表,键为排序后的字符串,值为原始字符串列表。
  2. 遍历字符串数组

    • 对每个字符串进行排序,并将排序后的字符串作为键,原始字符串添加到对应的列表中。
  3. 返回结果

    • 将哈希表的值转换为列表并返回。

复杂度分析

  • 时间复杂度:O(n * k log k),其中 n 是字符串数组的长度,k 是字符串的最大长度。排序每个字符串的时间复杂度为 O(k log k)。
  • 空间复杂度:O(n * k),用于存储哈希表。

示例运行

示例1
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例2
输入: strs = [""]
输出: [[""]]
示例3
输入: strs = ["a"]
输出: [["a"]]

优化思路

如果字符串长度较短,可以使用字符计数作为哈希表的键,进一步优化时间复杂度。

优化代码
def groupAnagrams_optimized(strs):from collections import defaultdictanagrams = defaultdict(list)for s in strs:# 使用字符计数作为键count = [0] * 26for char in s:count[ord(char) - ord('a')] += 1# 将字符计数转换为元组(因为列表不能作为哈希表的键)anagrams[tuple(count)].append(s)return list(anagrams.values())# 测试示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]print(groupAnagrams_optimized(strs1))  # 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams_optimized(strs2))  # 输出: [[""]]
print(groupAnagrams_optimized(strs3))  # 输出: [["a"]]

优化代码解析

  1. 字符计数

    • 使用长度为26的列表记录每个字符的出现次数。
    • 将字符计数转换为元组(因为列表不能作为哈希表的键)。
  2. 时间复杂度

    • 时间复杂度为 O(n * k),其中 n 是字符串数组的长度,k 是字符串的最大长度。

总结

通过使用哈希表,我们可以高效地将字母异位词分组。排序法和字符计数法各有优劣,可以根据实际需求选择合适的方法。希望这篇题解对大家有所帮助,如果有任何问题,欢迎在评论区留言讨论!

关注我,获取更多算法题解和编程技巧!

关键字:长春大学_关于三亚的网页设计_软文营销的技巧有哪些_网站如何优化排名软件

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: