leetcode热题100. 字母异位词分组

简介: leetcode热题100. 字母异位词分组

题目

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入:

strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出:

[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示:

1 < = s t r s . l e n g t h < = 1 0 4 1 <= strs.length <= 10^41<=strs.length<=104

0 < = s t r s [ i ] . l e n g t h < = 100 0 <= strs[i].length <= 1000<=strs[i].length<=100

strs[i] 仅包含小写字母

思路

将每一个字符串排序,将排好序的字符串当作key,然后存入一个字典中。

这样做的话,对于所有的字母异位词来说就都只有一个共同的key,然后可将他们当作一组添加到答案中

复杂度

时间复杂度:

O ( n ) O(n)O(n)

空间复杂度:

O ( n ) O(n)O(n)

Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        n = len(strs)
        for i in range(n):
            key = str( sorted(strs[i]) )
            dic[key].append(strs[i])
        
        ans = [i for i in dic.values()]
        return ans


目录
相关文章
|
21小时前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
21小时前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
4天前
|
存储 算法 安全
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
|
4天前
|
存储 算法 数据挖掘
leetcode第十七题:解密电话号码的字母组合与应用【python】
leetcode第十七题:解密电话号码的字母组合与应用【python】
|
8天前
|
存储 算法 Java
【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)
【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)
9 0
|
23天前
|
Windows
力扣100097. 合法分组的最少组数(哈希+贪心)
力扣100097. 合法分组的最少组数(哈希+贪心)
|
30天前
leetcode代码记录(第一个出现两次的字母
leetcode代码记录(第一个出现两次的字母
16 2
|
18天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
21 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
6天前
|
存储 算法
力扣链表刷题总结(简单)
力扣链表刷题总结(简单)
|
17天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
21 0