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