題目描述：
給定一個字符串數組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"],
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
說明：
- 所有輸入均為小寫字母。
- 不考慮答案輸出的順序。
方法一、排序數組分類：
思路
當且僅當它們的排序字符串相等時，兩個字符串是字母異位詞。
算法
維護一個映射 ans : {String -> List}，其中每個鍵 K 是一個排序字符串，每個值是初始輸入的字符串列表，排序後等於 K。
在 Java 中，我們將鍵存儲為字符串，例如，code。 在 Python 中，我們將鍵存儲為散列化元組，例如，('c', 'o', 'd', 'e')。
Java 代碼實現
Python 代碼實現
複雜度分析
- 時間複雜度：O(N K log K)，其中 N 是 strs 的長度，而 K 是 strs 中字符串的最大長度。當我們遍歷每個字符串時，外部循環具有的複雜度為 O(N)。然後，我們在 O(K log K) 的時間內對每個字符串排序。
- 空間複雜度：O(N K)，排序存儲在 ans 中的全部信息內容。
方法二、按計數分類：
思路
當且僅當它們的字符計數（每個字符的出現次數）相同時，兩個字符串是字母異位詞。
算法
我們可以將每個字符串 ss 轉換為字符數 count，由26個非負整數組成，表示 a，b，c 的數量等。我們使用這些計數作為哈希映射的基礎。
在 Java 中，我們的字符數 count 的散列化表示將是一個用 **＃** 字符分隔的字符串。 例如，abbccc 將表示為 ＃1＃2＃3＃0＃0＃0 ...＃0，其中總共有26個條目。 在 python 中，表示將是一個計數的元組。 例如，abbccc 將表示為 (1,2,3,0,0，...，0)，其中總共有 26 個條目。
Java 代碼實現
Python 代碼實現
複雜度分析
- 時間複雜度：O(N K)，其中 NN 是 strs 的長度，而 K 是 strs 中字符串的最大長度。計算每個字符串的字符串大小是線性的，我們統計每個字符串。
- 空間複雜度：O(N K)，排序存儲在 ans 中的全部信息內容。
分享到:
閱讀更多 領釦網 的文章
