LeetCode

Appearance

49. Group Anagrams ​

题目 ​

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

  • There is no string in strs that can be rearranged to form "bat".
  • The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
  • The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

 

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.
Related Topics
  • 数组
  • 哈希表
  • 字符串
  • 排序

  • 👍 2290
  • 👎 0

    • 思路 ​

    对每个字符串进行排序，然后用 hashmap 存储下排过序列的字符串

    • 若排序后的字符串存在，则存在对应的字符串的数组中
    • 若字符串不存在，则结果数组中新增一数组

    解法 ​

    python
    
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = []
        hashmap = {}
        for word in strs:
            sorted_str = ''.join(sorted(word))
            if sorted_str in hashmap:
                res[hashmap[sorted_str]].append(word)
            else:
                hashmap[sorted_str] = len(res)
                res.append([word])

        return res

    复杂度分析 ​

    • 时间复杂度 O(N * MlogM)
      • 假定字符串长度是 M, 字符串排序的时间复杂度为 M logM
      • N 个字符串遍历需要时间为 N
      • 故总的时间复杂度为 O(N*MlogM)
    • 空间复杂度 O(N*M)
      • hashmap 所需要的存储空间为O(N)

    解法二 ​

    通过使用 defaultDict(list) 可直接创建出目标数组，最后通过 list(hashmap.values())转换成结果的数组格式

    py
    # leetcode submit region begin(Prohibit modification and deletion)
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = defaultdict(list)
        for word in strs:
            sorted_str = ''.join(sorted(word))
            hashmap[sorted_str].append(word)
        return list(hashmap.values())
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N* MlogM)
    • 空间复杂度 O(N*M)