你是不是也遇到過這樣的場景面試時被問到“如何將一組字符串按字母異位詞分組”腦子里瞬間閃過“排序”、“哈希表”這些關鍵詞但真到寫代碼時卻卡在細節(jié)上——排序用哪種方式效率最高哈希表的鍵怎么設計才能既保證正確性又兼顧性能為什么有些解法看似簡單但在力扣LeetCode上提交卻總是超時今天要徹底講清楚的正是力扣第49題《字母異位詞分組》。這道題在各大公司的面試中出場率極高不是因為它多難而是因為它完美考察了候選人對哈希表和字符串排序這兩個基礎數(shù)據(jù)結構和算法的理解深度以及將理論轉(zhuǎn)化為高效、健壯代碼的工程能力。很多人以為會寫個排序再分組就過關了但實際上從鍵的設計、排序算法的選擇到字符計數(shù)的優(yōu)化每一步都藏著區(qū)分“普通解”和“最優(yōu)解”的關鍵。本文將帶你從問題本質(zhì)出發(fā)一步步推導出最高效的解法。你會看到我們不僅會寫出能通過的代碼更要寫出在面試官面前能拿高分的代碼。我們將深入探討為什么哈希表是解決此類分組問題的“銀彈”排序和字符計數(shù)兩種主流方法各自的適用場景和性能瓶頸在哪里如何從O(nklogk)的復雜度優(yōu)化到接近O(nk)這里面的“k”究竟是什么面對包含Unicode字符的字符串我們的解法還成立嗎更重要的是我會提供可直接運行、逐行注釋的代碼示例Python/Java并附上詳細的復雜度分析和常見“坑點”排查。無論你是正在刷題準備面試的“小白”還是想鞏固基礎的開發(fā)者這篇文章都能讓你對“字母異位詞分組”及其背后的思想有全新的認識。1. 這道題到底在考什么為什么它如此重要在力扣上題目《49. 字母異位詞分組》的描述很簡單給你一個字符串數(shù)組strs請你將字母異位詞組合在一起?？梢园慈我忭樞蚍祷卮鸢?。一個簡單的例子 輸入strs [eat, tea, tan, ate, nat, bat]輸出[[bat],[nat,tan],[ate,eat,tea]]字母異位詞的定義是重新排列源單詞的所有字母得到的新單詞。所以“eat”、“tea”、“ate”互為字母異位詞。表面看這是一道簡單的分組題。但它的重要性體現(xiàn)在三個層面第一它是“哈希表”應用的經(jīng)典范本。哈希表散列表的核心思想是“鍵-值”映射其靈魂在于“鍵”的設計。這道題逼著你思考用什么作為哈希表的鍵才能讓異位詞映射到同一個值直接使用原字符串顯然不行。排序后的字符串這是一個選擇。字符計數(shù)數(shù)組這是另一個更底層的選擇。這個“鍵設計”的過程直接考察了你對問題本質(zhì)的抽象能力。第二它串聯(lián)了“排序”和“字符串處理”兩大基礎技能。無論采用哪種鍵設計都繞不開對字符串內(nèi)字符的處理。是用內(nèi)置的排序函數(shù)還是自己實現(xiàn)計數(shù)排序這背后是對時間復雜度的權衡。字符串的不可變性、字符的編碼方式ASCII vs Unicode都會影響實現(xiàn)細節(jié)。第三它是面試中區(qū)分“背題”和“真懂”的試金石。很多候選人能背出“排序哈希表”的模板代碼。但優(yōu)秀的面試官會追問“如果字符串很長比如長度k1000排序還高效嗎”“如果字符串只包含小寫字母有沒有更快的辦法”“你的解法能處理包含空格或標點的字符串嗎”“請分析一下你算法的時間和空間復雜度。”如果你只停留在套模板這些問題很容易讓你露怯。而本文的目標就是讓你不僅能寫出代碼更能對答如流展現(xiàn)出扎實的計算機基礎。2. 核心概念拆解哈希表、排序與字母異位詞在深入代碼之前我們必須統(tǒng)一理解幾個核心概念這是寫出正確、高效代碼的前提。2.1 哈希表為什么它是分組問題的“萬能鑰匙”哈希表是一種通過“鍵”快速訪問“值”的數(shù)據(jù)結構。它的平均時間復雜度是O(1)這意味著無論里面存了多少數(shù)據(jù)查找、插入的速度都極快。在這道題里我們的目標是“分組”。邏輯是遍歷每個字符串把它放到對應的組里。如果沒有哈希表你可能需要為每個字符串去和已有所有組比較看是否匹配時間復雜度會是O(n2)。哈希表改變了游戲規(guī)則。我們設計一個“鍵”讓所有字母異位詞都計算出相同的鍵。這樣我們只需要計算當前字符串的“鍵”。去哈希表里找這個鍵對應的“組”值。如果組不存在就新建一個如果存在就把當前字符串加進去。這個過程的時間消耗主要在“計算鍵”和“哈希表操作”上而哈希表操作是近似O(1)的。因此整體效率取決于我們計算鍵的速度。2.2 字母異位詞的數(shù)學本質(zhì)字符的多重集合從數(shù)學角度看一個字符串可以看作一個多重集合其中的元素是字符每個字符有它的出現(xiàn)次數(shù)。兩個字符串是字母異位詞當且僅當它們對應的字符多重集合完全相同。例如“eat”和“tea”“eat” - {‘e’:1, ‘a(chǎn)’:1, ‘t’:1}“tea” - {‘t’:1, ‘e’:1, ‘a(chǎn)’:1}這兩個集合是完全一樣的。因此判斷兩個字符串是否為字母異位詞等價于判斷它們的字符計數(shù)是否一致。這為我們提供了兩種設計哈希表鍵的思路排序鍵將字符串排序異位詞排序后必然相同。例如“eat”、“tea”、“ate”排序后都是“aet”。計數(shù)鍵統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)將這個計數(shù)數(shù)組或它的某種表示如字符串作為鍵。2.3 排序快速排序 vs 計數(shù)排序當我們選擇“排序鍵”時需要對每個字符串進行排序。通常我們調(diào)用語言內(nèi)置的排序函數(shù)如Python的sortedJava的Arrays.sort它們一般使用快速排序或其變種時間復雜度為O(k log k)其中k是字符串的長度。但是如果題目明確說明字符串只包含小寫字母這是一個常見且重要的條件我們就有了優(yōu)化空間。小寫字母只有26種可能我們可以使用計數(shù)排序這是一種特殊的非比較排序算法時間復雜度可以達到O(k 26) ≈ O(k)。在k很大時這比O(k log k)快得多。理解這些概念后我們就可以開始動手了。接下來我們從最直觀的解法開始逐步優(yōu)化。3. 方法一排序 哈希表通用解法這是最直接、最容易想到的方法也是面試中你應該首先闡述的解法。它的適用性最廣不依賴于字符集。思路遍歷字符串數(shù)組中的每個字符串。對每個字符串將其字符排序得到一個新的字符串作為“鍵”。以這個“鍵”去哈希表中查找對應的列表。將原始字符串添加到該列表中。遍歷完成后哈希表中所有的值就是我們要的分組結果。3.1 Python實現(xiàn)from typing import List from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: 使用排序作為哈希表的鍵來分組字母異位詞。 時間復雜度O(n * k log k)其中n是字符串個數(shù)k是字符串最大長度。 空間復雜度O(n * k)哈希表存儲所有字符串。 # 使用defaultdict(list)當鍵不存在時會自動創(chuàng)建一個空列表作為值 anagram_map defaultdict(list) for s in strs: # 關鍵步驟將字符串排序并轉(zhuǎn)換為元組作為不可變的鍵 # sorted(s) 返回字符列表例如 eat - [a, e, t] # tuple() 將其轉(zhuǎn)換為可哈希的元組 key tuple(sorted(s)) # 將原字符串s添加到該鍵對應的列表中 anagram_map[key].append(s) # 返回哈希表中所有的值即分組列表 return list(anagram_map.values()) # 測試代碼 if __name__ __main__: solution Solution() test_strs [eat, tea, tan, ate, nat, bat] result solution.groupAnagrams(test_strs) print(分組結果, result) # 輸出 [[eat, tea, ate], [tan, nat], [bat]] (順序可能不同)代碼解讀與注意事項鍵的選擇我們使用tuple(sorted(s))作為鍵。為什么不用sorted(s)直接作為鍵因為在Python中列表是可變對象不可哈希不能作為字典的鍵。必須轉(zhuǎn)換為元組。使用defaultdict這簡化了代碼。如果不使用你需要先判斷鍵是否存在if key not in map: map[key] []然后再map[key].append(s)。復雜度分析時間遍歷n個字符串是O(n)。對每個長度為k的字符串排序是O(k log k)。所以總時間是O(n * k log k)。空間哈希表需要存儲所有n個字符串以及它們的鍵。最壞情況下沒有異位詞每個字符串的鍵都不同需要存儲所有字符串和鍵所以是O(n * k)。3.2 Java實現(xiàn)import java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { // 哈希表鍵為排序后的字符串值為原始字符串列表 MapString, ListString map new HashMap(); for (String s : strs) { // 將字符串轉(zhuǎn)換為字符數(shù)組并排序 char[] charArray s.toCharArray(); Arrays.sort(charArray); // 將排序后的字符數(shù)組轉(zhuǎn)換回字符串作為鍵 String key new String(charArray); // 如果鍵不存在則創(chuàng)建一個新列表 map.putIfAbsent(key, new ArrayList()); // 將當前字符串添加到對應的列表中 map.get(key).add(s); } // 返回哈希表中所有值的集合即分組結果 return new ArrayList(map.values()); } // 測試 public static void main(String[] args) { Solution sol new Solution(); String[] strs {eat, tea, tan, ate, nat, bat}; ListListString result sol.groupAnagrams(strs); System.out.println(分組結果: result); // 輸出可能為[[eat, tea, ate], [tan, nat], [bat]] } }Java版本關鍵點String.toCharArray()和Arrays.sort()是標準操作。map.putIfAbsent(key, new ArrayList())是Java 8的便捷方法等同于Pythondefaultdict的部分功能。最后通過new ArrayList(map.values())返回結果。注意map.values()返回的是CollectionListString需要包裝成ArrayList以滿足返回類型。這個方法簡單明了是面試時的保底答案。但面試官通常會接著問“如果字符串很長排序開銷大有沒有更優(yōu)的方法” 這就引出了我們的第二種方法。4. 方法二字符計數(shù) 哈希表優(yōu)化解法當題目明確字符串僅包含小寫字母時我們可以利用這個約束進行大幅優(yōu)化。我們不再排序而是統(tǒng)計每個字母出現(xiàn)的次數(shù)用這個計數(shù)數(shù)組作為哈希表的鍵。為什么這樣更快排序一個長度為k的字符串需要O(k log k)時間。而統(tǒng)計26個小寫字母的出現(xiàn)次數(shù)只需要遍歷一次字符串是O(k)時間。當k很大時O(k)顯著優(yōu)于O(k log k)。思路準備一個長度為26的數(shù)組count對應26個小寫字母。遍歷字符串的每個字符在count對應位置加1。將這個count數(shù)組轉(zhuǎn)換為一個唯一的字符串表示例如用#連接每個計數(shù)作為哈希表的鍵。后續(xù)步驟與方法一相同。4.1 Python實現(xiàn)字符計數(shù)from typing import List from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: 使用字符計數(shù)作為哈希表的鍵。 前提strs[i] 僅包含小寫字母。 時間復雜度O(n * k)其中n是字符串個數(shù)k是字符串最大長度。 空間復雜度O(n * k)。 anagram_map defaultdict(list) for s in strs: # 初始化一個長度為26的計數(shù)數(shù)組所有元素為0 count [0] * 26 for char in s: # 利用ord函數(shù)將字符轉(zhuǎn)換為ASCII碼減去‘a(chǎn)’的ASCII得到索引(0-25) count[ord(char) - ord(a)] 1 # 關鍵將計數(shù)數(shù)組轉(zhuǎn)換為一個唯一的字符串作為鍵。 # 使用‘#’連接是為了防止計數(shù)數(shù)字混淆。 # 例如count [1,1,0,...,1] - “1#1#0...#1” key #.join(str(c) for c in count) anagram_map[key].append(s) return list(anagram_map.values()) # 測試 if __name__ __main__: solution Solution() test_strs [eat, tea, tan, ate, nat, bat] result solution.groupAnagrams(test_strs) print(分組結果計數(shù)法:, result)代碼細節(jié)分析ord(char) - ord(a)這是將小寫字母映射到0-25索引的標準技巧。ord(a)是97ord(b)是98以此類推。鍵的構造‘#’.join(str(c) for c in count)。為什么不用tuple(count)因為列表本身不可哈希。為什么要把數(shù)組轉(zhuǎn)換成字符串因為數(shù)組是可變的不能直接作為鍵。這個字符串如“1#0#0...#2”唯一地標識了字符頻率。復雜度時間外層循環(huán)O(n)內(nèi)層對每個字符串遍歷一次O(k)構造鍵O(26)O(1)。所以總時間是O(n * k)?？臻g與方法一類似為O(n * k)。4.2 Java實現(xiàn)字符計數(shù)import java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; // 字符相減得到索引 } // 構建鍵將計數(shù)數(shù)組轉(zhuǎn)換為一個特征字符串 StringBuilder keyBuilder new StringBuilder(); for (int i 0; i 26; i) { keyBuilder.append(#); keyBuilder.append(count[i]); } String key keyBuilder.toString(); map.putIfAbsent(key, new ArrayList()); map.get(key).add(s); } return new ArrayList(map.values()); } // 測試 public static void main(String[] args) { Solution sol new Solution(); String[] strs {eat, tea, tan, ate, nat, bat}; ListListString result sol.groupAnagrams(strs); System.out.println(分組結果計數(shù)法: result); } }性能對比與選擇方法一排序通用性強適用于任何字符集包括大寫、數(shù)字、符號。但當字符串很長時O(k log k)的排序可能成為瓶頸。方法二計數(shù)僅適用于字符集有限且已知的情況如小寫字母。它的時間復雜度O(n*k)在k較大時更優(yōu)。但構造鍵StringBuilder操作也有開銷對于非常短的字符串可能不如排序法直接。面試策略通常先給出通用解法方法一然后主動提出“如果題目限定為小寫字母我們可以用字符計數(shù)法進一步優(yōu)化到O(n*k)”并闡述方法二。這展示了你的思維層次和對性能的敏感度。5. 運行結果與效果驗證無論用哪種方法對于示例輸入[eat,tea,tan,ate,nat,bat]我們期望的輸出是一個列表包含三個子列表分別對應三組異位詞。順序不重要。我們可以編寫更全面的測試來驗證代碼的健壯性。# 擴展測試用例 def test_group_anagrams(): solution Solution() # 假設使用計數(shù)法的Solution類 test_cases [ { input: [eat, tea, tan, ate, nat, bat], expected_outputs: [[bat], [nat, tan], [ate, eat, tea]] # 忽略內(nèi)部順序 }, { input: [], expected_outputs: [[]] }, { input: [a], expected_outputs: [[a]] }, { input: [cab, tin, pew, duh, may, buy, bar, abc], # cab和abc是異位詞其余均單獨成組 expected_outputs: [[cab, abc], [tin], [pew], [duh], [may], [buy], [bar]] } ] for i, test_case in enumerate(test_cases): input_strs test_case[input] result solution.groupAnagrams(input_strs) # 由于輸出順序和組內(nèi)順序不確定我們需要規(guī)范化結果以便比較 normalized_result [] for group in result: normalized_result.append(sorted(group)) # 對每個組內(nèi)排序 normalized_result.sort() # 對組間排序 normalized_expected [] for group in test_case[expected_outputs]: normalized_expected.append(sorted(group)) normalized_expected.sort() if normalized_result normalized_expected: print(f測試用例 {i1} 通過: 輸入{input_strs} - 輸出{result}) else: print(f測試用例 {i1} 失敗!) print(f 輸入: {input_strs}) print(f 期望: {normalized_expected}) print(f 實際: {normalized_result}) return False print(所有測試用例通過) return True if __name__ __main__: test_group_anagrams()驗證要點邊界情況空字符串[]和單字符[a]需要正確處理。無重復詞所有字符串都互不為異位詞時應返回每個字符串單獨成組。順序無關性比較結果時必須對組內(nèi)和組間進行排序確保邏輯正確而非順序正確。字符集確保測試用例符合算法假設如計數(shù)法只測小寫字母。運行上述測試如果全部通過說明你的算法邏輯是正確的。6. 復雜度深度分析與對比理解算法復雜度不僅是面試要求更是選擇合適解法的依據(jù)。我們來詳細拆解方法時間復雜度空間復雜度適用場景排序哈希表O(n * k log k)O(n * k)通用場景字符集不限。k較小時很高效。計數(shù)哈希表O(n * k)O(n * k)僅限字符集固定且較小如26個小寫字母。k很大時優(yōu)勢明顯。詳細解釋n: 字符串數(shù)組的長度。k: 每個字符串的平均長度或最大長度在Big-O表示法中常取最大長度。O(n * k log k):n次循環(huán)每次循環(huán)中對長度為k的字符串排序O(k log k)。O(n * k):n次循環(huán)每次循環(huán)中遍歷字符串O(k)和構造固定長度的鍵O(26)O(1)。注意一個常見的誤區(qū)有些人會說是O(n * k log k) vs O(n * 26)或O(n)。這是不對的。計數(shù)法中的O(n * k)來自于遍歷每個字符串的每個字符這是必須的。O(26)只是構造鍵的額外開銷。所以當k很小比如1或2時排序法可能更快因為O(k log k)和O(k)差別不大而排序是高度優(yōu)化的本地操作。但當k增長到1000時O(1000 log 1000) ≈ O(10000) 和 O(1000) 的差距就非常顯著了。結論在力扣這道題的標準環(huán)境下字符串長度不會極端兩種方法通常都能通過。但計數(shù)法展示了更強的算法優(yōu)化意識是面試中的加分項。7. 常見問題與排查思路在實際編碼或面試中你可能會遇到以下問題問題現(xiàn)象可能原因排查方式解決方案輸出結果為空列表或分組錯誤1. 哈希表的鍵設計有誤導致異位詞未能映射到同一鍵。2. 在Python中使用了列表作為字典鍵。3. 字符計數(shù)數(shù)組索引計算錯誤非小寫字母。1. 打印出每個字符串計算出的鍵檢查異位詞的鍵是否相同。2. 檢查代碼中是否直接將sorted(s)列表用作鍵。3. 檢查輸入是否包含大寫字母或數(shù)字。1. 確保鍵是不可變且可哈希的如元組或字符串。2. 使用tuple(sorted(s))或‘’.join(sorted(s))。3. 確認題目約束或改用通用排序法。算法超時Time Limit Exceeded1. 使用了復雜度更高的算法如嵌套循環(huán)比較。2. 在鍵的生成上做了低效操作如在循環(huán)內(nèi)頻繁進行復雜字符串拼接。1. 分析代碼時間復雜度確保是O(n k log k)或O(n k)。2. 檢查是否在內(nèi)部有不必要的轉(zhuǎn)換或復制。1. 堅持使用哈希表避免O(n2)的比較。2. 對于計數(shù)法使用StringBuilderJava或列表推導式Python高效構建鍵。處理大寫字母或Unicode字符時失敗計數(shù)法默認只處理了小寫字母a-z。檢查輸入字符串。如果包含‘A’‘A‘ - ’a‘會產(chǎn)生負數(shù)索引。1.通用方案退回到排序法它對所有字符有效。2.擴展計數(shù)法如果字符集已知但更大如所有ASCII可擴大計數(shù)數(shù)組大小如128。但鍵會變得很長。返回結果中組內(nèi)順序與預期不符題目通常不要求組內(nèi)順序。你的輸出可能是[tea,eat,ate]而示例是[eat,tea,ate]。閱讀題目要求確認是否明確要求按某種順序輸出。如果題目沒有明確要求任何順序都是正確的。如果要求按字典序或輸入順序需要在最后對結果進行排序。內(nèi)存占用過高Memory Limit Exceeded1. 存儲了不必要的中間數(shù)據(jù)。2. 鍵的表示方式非常冗余如為每個字符串存儲了整個計數(shù)數(shù)組的副本。檢查哈希表中存儲的值。在計數(shù)法中鍵字符串的長度是固定的如26個數(shù)字加分隔符不會隨k增長。優(yōu)化鍵的表示。例如對于計數(shù)法可以用更緊湊的方式編碼計數(shù)數(shù)組如使用質(zhì)數(shù)乘積法見下文最佳實踐。8. 最佳實踐與進階優(yōu)化掌握了基本解法后我們來看看如何將代碼寫得更好、更魯棒以及一些更深入的優(yōu)化思路。8.1 鍵的優(yōu)化表示質(zhì)數(shù)乘積法在計數(shù)法中我們將計數(shù)數(shù)組轉(zhuǎn)換為“#1#0#0...#2”這樣的字符串作為鍵。當字符集很大時這個鍵會很長。一個巧妙的優(yōu)化是使用質(zhì)數(shù)。思路為每個字符分配一個唯一的質(zhì)數(shù)。將一個字符串中所有字符對應的質(zhì)數(shù)相乘得到的乘積作為鍵。由于質(zhì)數(shù)的唯一分解定理不同組合的字符得到的乘積一定不同而異位詞的乘積一定相同。from typing import List from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 前26個質(zhì)數(shù)分別對應a-z primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] anagram_map defaultdict(list) for s in strs: product 1 for char in s: # 計算質(zhì)數(shù)乘積 product * primes[ord(char) - ord(a)] # 使用乘積作為鍵 anagram_map[product].append(s) return list(anagram_map.values())優(yōu)點鍵是一個整數(shù)比字符串更緊湊比較和哈希更快。避免了字符串拼接操作。缺點與風險整數(shù)溢出乘積增長非?？臁＠缫粋€長字符串可能導致乘積超過語言中整型的最大值Python大整數(shù)沒問題但Java/C會溢出。在實際面試和力扣中不推薦使用此方法除非你能確保字符串很短或處理溢出。它更偏向于一種“炫技”的思路用于展示對數(shù)學原理的應用。8.2 使用frozenset僅適用于無重復字符的特殊情況這是一個錯誤示范但經(jīng)常被誤解。有人想用frozenset(Counter(s).items())作為鍵。Counter是字符計數(shù)frozenset是可哈希的。這聽起來很合理但對于有重復字符的字符串這方法是錯誤的。例如“aab”和“abb”“aab” - Counter({‘a(chǎn)’:2, ‘b’:1}) - items: [(‘a(chǎn)‘, 2), (‘b‘, 1)]“abb” - Counter({‘b’:2, ‘a(chǎn)’:1}) - items: [(‘b‘, 2), (‘a(chǎn)‘, 1)]它們的frozenset是相同的{(a, 2), (b, 1)}和{(b, 2), (a, 1)}嗎不(a, 2)和(b, 2)是不同的元組所以兩個frozenset不同。但如果字符頻率相同比如“aab”和“aba”它們的Counter items集合是相同的{(a, 2), (b, 1)}。然而frozenset丟失了順序(‘a(chǎn)‘, 2)和(‘b‘, 1)誰先誰后不影響集合相等。所以對于字符頻率相同的字符串即使字符不同用frozenset也會錯誤地判斷為異位詞。例如“aab”和“bba”頻率都是{‘a(chǎn)’:2, ‘b’:1}和{‘b’:2, ‘a(chǎn)’:1}items集合不同但frozenset后可能因為哈希順序看起來不同但邏輯上是錯誤的?？傊灰褂胒rozenset。8.3 工程化建議函數(shù)化與可測試性將核心邏輯封裝在函數(shù)內(nèi)便于單元測試。輸入驗證在生產(chǎn)代碼中應檢查輸入是否為None或空數(shù)組并返回適當值如空列表。文檔字符串為函數(shù)編寫清晰的文檔字符串說明前提條件、時間復雜度和空間復雜度。選擇穩(wěn)定的排序如果使用排序法在某些語言中要意識到排序的穩(wěn)定性不過本題中不影響結果。優(yōu)先使用標準庫collections.defaultdict和collections.Counter雖然這里Counter直接作為鍵有問題是Python的利器。Java中的Map.putIfAbsent和computeIfAbsent也很方便。8.4 面試回答模板當面試官問到這道題時你可以這樣組織回答闡述問題“這是一道經(jīng)典的哈希表應用題目標是將字母異位詞分組。字母異位詞是指字符重新排列后相同的單詞?！苯o出基礎解法“最直觀的解法是遍歷每個字符串將其字符排序用排序后的字符串作為哈希表的鍵原字符串作為值添加到對應列表中。時間復雜度是O(n k log k)空間O(n k)。這是通用解法。”提出優(yōu)化“如果題目限定字符串只包含小寫字母我們可以進一步優(yōu)化。用一個長度26的數(shù)組統(tǒng)計每個字符出現(xiàn)的次數(shù)然后將這個計數(shù)數(shù)組轉(zhuǎn)換成一個特征字符串如用‘#’連接作為鍵。這樣時間復雜度可以降到O(n * k)因為省去了排序的log k因子?！狈治鰧Ρ取芭判蚍ǖ膬?yōu)點是通用字符集不限。計數(shù)法在字符集小且字符串長時優(yōu)勢明顯。在實際選擇時需要根據(jù)題目約束來決定。”邊界情況“需要考慮空字符串、單字符、以及所有字符串都不同的情況。我們的算法都能正確處理?！笔謱懘a選擇一種方法寫出清晰、有注釋的代碼。9. 總結與擴展思考通過這道《字母異位詞分組》我們深入探討了哈希表在分組問題中的核心作用并對比了排序和計數(shù)兩種鍵設計策略。關鍵在于理解算法的核心在于如何為同一類對象生成一個唯一的、可哈希的標識符鍵。這道題的價值遠不止于通過一道力扣題。它教會我們數(shù)據(jù)轉(zhuǎn)換思維將復雜的對象字符串轉(zhuǎn)換為簡單的、可比較的中間表示排序串或計數(shù)數(shù)組?？臻g換時間利用哈希表O(1)的查找能力將潛在的O(n2)比較問題降為O(n)或O(n k)的遍歷問題。約束條件利用題目中“只包含小寫字母”這樣的約束不是白給的它是性能優(yōu)化的突破口。下一步你可以這樣鞏固和擴展舉一反三嘗試解決力扣第242題《有效的字母異位詞》這是本題的單次版本。第438題《找到字符串中所有字母異位詞》則使用了滑動窗口和計數(shù)數(shù)組是本題思想的延伸。挑戰(zhàn)自己如果字符串包含Unicode字符范圍很大如何高效分組這時排序法可能是唯一選擇但思考如何優(yōu)化排序過程或鍵的存儲。系統(tǒng)學習以本題為起點系統(tǒng)學習哈希表相關的其他題目如《兩數(shù)之和》、《三數(shù)之和》、《最長連續(xù)序列》等體會哈希表在不同場景下的妙用。最后記住在面試或?qū)嶋H開發(fā)中清晰比聰明更重要。首先給出正確、清晰的解法然后根據(jù)條件逐步優(yōu)化并清楚地說出每個選擇的權衡。這道題的精髓你已經(jīng)掌握了。