LeetCode 49(字母异位词分组)题解

警告
本文最后更新于 2023-02-06,文中内容可能已过时。

Leetcode 49 题

题干简述

  1. 给定:一字符串数组。
  2. 要求:将字符串分组,组成元素相同的分为一组,比如 eat 与 tea。

详情请看:https://leetcode.cn/problems/group-anagrams/?favorite=2cktkvj

解题思路

  1. 同一组的字符串有一个特点:字符类型相同但顺序不同。
  2. 根据这一特点,我们将所有字符串依照字母顺序排序(a->z),比如 eat、tea 排序后变成 aet,从而很容易判断出 eat 与 tea 为同一组。

图解算法

img.png

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = dict()

        for str in (strs):
            strSortedList = list(str)
            strSortedList.sort()
            strSorted = "".join(strSortedList)

            if strSorted in res:
                res[strSorted].append(str)
            else:
                res[strSorted] = [str]

        return res.values()

复杂度

img.png

Buy me a coffee~
室长 支付宝支付宝
室长 微信微信
0%