給定一個字符串數組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。

示例:

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"] 輸出: [["ate","eat","tea"],["nat","tan"],["bat"] ]

說明：

• 所有輸入均為小寫字母。
• 不考慮答案輸出的順序。

排序

由于互為字母異位詞的兩個字符串包含的字母相同，因此對兩個字符串分別進行排序之后得到的字符串一定是相同的，故可以將排序之后的字符串作為哈希表的鍵。

Python

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:ans = collections.defaultdict(list)for word in strs:key = "".join(sorted(word))ans[key].append(word)return list(ans.values())

復雜度分析

• 時間復雜度：$O(nk\log k)$，其中 $n$ 是 $\text{strs}$ 中的字符串的數量，$k$ 是 $\text{strs}$ 中的字符串的的最大長度。需要遍歷 $n$ 個字符串，對于每個字符串，需要 $O(k\log k)$ 的時間進行排序以及 $O(1)$ 的時間更新哈希表，因此總時間復雜度是 $O(nk\log k)$。

• 空間復雜度：$O(nk)$，其中 $n$ 是 $\text{strs}$ 中的字符串的數量，$k$ 是 $\text{strs}$ 中的字符串的的最大長度。需要用哈希表存儲全部字符串。

總結

以上是生活随笔為你收集整理的《每日一题》49. Group Anagrams 字母异位词分组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。