LeetCode 熱題 100 | 49. 字母異位詞分組

大家好，今天我們來(lái)解決一道經(jīng)典的算法題——字母異位詞分組。這道題在LeetCode上被標(biāo)記為中等難度，要求我們將字母異位詞組合在一起。下面我將詳細(xì)講解解題思路，并附上Python代碼實(shí)現(xiàn)。

---

問題描述

給定一個(gè)字符串?dāng)?shù)組 strs，將其中所有字母異位詞組合在一起。字母異位詞是指由相同字母重新排列形成的單詞。

示例：

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

---

解題思路

核心思想

1. 哈希表分組：

   • 使用哈希表（字典）來(lái)存儲(chǔ)字母異位詞的分組結(jié)果。
   • 將每個(gè)字符串排序后的結(jié)果作為哈希表的鍵，原始字符串作為值。

2. 排序作為鍵：

   • 由于字母異位詞排序后的結(jié)果相同，可以將排序后的字符串作為哈希表的鍵。

3. 返回結(jié)果：

   • 遍歷哈希表的值，將分組結(jié)果存入列表并返回。

---

Python代碼實(shí)現(xiàn)

def groupAnagrams(strs):from collections import defaultdict# 使用 defaultdict 初始化哈希表anagrams = defaultdict(list)# 遍歷字符串?dāng)?shù)組for s in strs:# 將字符串排序后作為鍵sorted_s = ''.join(sorted(s))# 將原始字符串添加到對(duì)應(yīng)的分組中anagrams[sorted_s].append(s)# 返回分組結(jié)果return list(anagrams.values())# 測(cè)試示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]print(groupAnagrams(strs1))  # 輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams(strs2))  # 輸出: [[""]]
print(groupAnagrams(strs3))  # 輸出: [["a"]]

---

代碼解析

1. 哈希表初始化：

   • 使用 defaultdict(list) 創(chuàng)建一個(gè)哈希表，鍵為排序后的字符串，值為原始字符串列表。

2. 遍歷字符串?dāng)?shù)組：

   • 對(duì)每個(gè)字符串進(jìn)行排序，并將排序后的字符串作為鍵，原始字符串添加到對(duì)應(yīng)的列表中。

3. 返回結(jié)果：

   • 將哈希表的值轉(zhuǎn)換為列表并返回。

---

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n * k log k)，其中 n 是字符串?dāng)?shù)組的長(zhǎng)度，k 是字符串的最大長(zhǎng)度。排序每個(gè)字符串的時(shí)間復(fù)雜度為 O(k log k)。
• 空間復(fù)雜度：O(n * k)，用于存儲(chǔ)哈希表。

---

示例運(yùn)行

示例1

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

示例2

輸入: strs = [""]
輸出: [[""]]

示例3

輸入: strs = ["a"]
輸出: [["a"]]

---

優(yōu)化思路

如果字符串長(zhǎng)度較短，可以使用字符計(jì)數(shù)作為哈希表的鍵，進(jìn)一步優(yōu)化時(shí)間復(fù)雜度。

優(yōu)化代碼

def groupAnagrams_optimized(strs):from collections import defaultdictanagrams = defaultdict(list)for s in strs:# 使用字符計(jì)數(shù)作為鍵count = [0] * 26for char in s:count[ord(char) - ord('a')] += 1# 將字符計(jì)數(shù)轉(zhuǎn)換為元組（因?yàn)榱斜聿荒茏鳛楣１淼逆I）anagrams[tuple(count)].append(s)return list(anagrams.values())# 測(cè)試示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]print(groupAnagrams_optimized(strs1))  # 輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams_optimized(strs2))  # 輸出: [[""]]
print(groupAnagrams_optimized(strs3))  # 輸出: [["a"]]

---

優(yōu)化代碼解析

1. 字符計(jì)數(shù)：

   • 使用長(zhǎng)度為26的列表記錄每個(gè)字符的出現(xiàn)次數(shù)。
   • 將字符計(jì)數(shù)轉(zhuǎn)換為元組（因?yàn)榱斜聿荒茏鳛楣１淼逆I）。

2. 時(shí)間復(fù)雜度：

   • 時(shí)間復(fù)雜度為 O(n * k)，其中 n 是字符串?dāng)?shù)組的長(zhǎng)度，k 是字符串的最大長(zhǎng)度。

---

總結(jié)

通過使用哈希表，我們可以高效地將字母異位詞分組。排序法和字符計(jì)數(shù)法各有優(yōu)劣，可以根據(jù)實(shí)際需求選擇合適的方法。希望這篇題解對(duì)大家有所幫助，如果有任何問題，歡迎在評(píng)論區(qū)留言討論！

關(guān)注我，獲取更多算法題解和編程技巧！