規(guī)劃的完整推導(dǎo)與優(yōu)化)
前幾天在群里看到有人問LeetCode 139這道單詞拆分說自己花了大半小時寫了套遞歸樣例全過一提交就超時。這問題我太有共鳴了——當年我刷LeetCode 139單詞拆分的時候同樣在“怎么把遞歸改成動態(tài)規(guī)劃”這一步卡了兩天。今天這篇不想只貼一份標準答案糊弄人我想把這道題從暴力遞歸到動態(tài)規(guī)劃再到BFS的完整推導(dǎo)過程、邊界條件、還有我實測下來踩過的性能坑一次性講清楚。如果你正在刷LeetCode熱門100題或者準備面試時遇到字符串相關(guān)的動態(tài)規(guī)劃題目這篇應(yīng)該能幫你省下不少彎路。1. 題目拆解讀懂“可拆分”到底在問什么1.1 三個樣例分別埋了哪些坑LeetCode 139給的標準樣例其實埋了三個層次的陷阱我一個個拆開說。第一個樣例s leetcode字典 [leet, code]返回 true。這是最簡單的線性拆分從前往后切一刀就行對應(yīng)到代碼里就是“s[0:4]在字典里s[4:8]也在字典里”。這里唯一要注意的是Java中substring是左閉右開substring(0, 4)取到的是leetsubstring(4, 8)取到的是code。這個邊界問題寫錯的人特別多尤其是從C轉(zhuǎn)過來的同學習慣了左閉右開還好第一次寫Java的時候很容易把endIndex寫成4。第二個樣例s applepenapple字典 [apple, pen]返回 true。這個樣例想說的關(guān)鍵信息是同一個單詞可以在拆分結(jié)果里重復(fù)出現(xiàn)。也就是說字典里的每個單詞使用次數(shù)沒有限制你可以無窮次地使用它只要最后拼出來的字符串等于s就行。這一點非常重要因為它直接決定了我們不需要在狀態(tài)里記錄“哪個單詞用過了”——這是很多人在思考時被卡住的地方。第三個樣例s catsandog字典 [cats, dog, sand, and, cat]返回 false。這個樣例是專門用來坑人的從cats開始拆可以拆出cats、and、og但og不在字典里從cat開始拆后面是sandog怎么切都切不像。它想表達的是局部匹配成功不代表整體能成功你沒法用貪心算法從頭掃到尾取一個能匹配的就完事。這個反例后面面試講題時經(jīng)常被追問最好背下來。1.2 判定問題先于方案列舉我在帶人刷題的時候發(fā)現(xiàn)一個規(guī)律凡是第一次看到這道題能直接寫對的人基本都是先意識到了它是一個判定問題。題目問的是“能不能被拆分成若干個單詞”不是“有幾種拆分方式”更不是“把每一種拆分方式都列出來”。這個區(qū)別決定了算法走向判定問題可以只保留“行/不行”這個布爾信息把中途所有詳細的拆分過程全部扔掉。舉個例子假設(shè)你正站在第j個字符的位置前面已經(jīng)拆到這兒了你不需要關(guān)心前面具體是被拆成了[leet,co]還是[le,etc,od]——你只需要知道“能不能拆到第j個字符”這一個事實。一旦這個事實確定了后面怎么拆就只跟當前下標j有關(guān)跟之前的路徑完全無關(guān)。這就是動態(tài)規(guī)劃很喜歡講的“無后效性”也是這道題能從指數(shù)級的暴力枚舉優(yōu)化到多項式時間的關(guān)鍵。很多新手在這里會糾結(jié)如果前面的具體拆分方式不同后面能匹配的單詞會不會不同答案是不會。因為字典匹配只看從j開始的那段子串不關(guān)心j之前的內(nèi)容是什么。這個思維轉(zhuǎn)換是字符串動態(tài)規(guī)劃題目的通用判斷標準不光139用得上132、140那一類題都靠這個邏輯。1.3 一個容易翻車的邊界dp[0]哨兵值幾乎所有題解都會直接說dp[0] true但很少有人解釋為什么。我的理解是一個空前綴本身不需要拆分它天然是“可選起點”。你可以把任何一次成功的拆分看作“從前一個位置出發(fā)拼了某個單詞”而起始位置0要能出發(fā)就得先有一個dp[0] true作為起點。反過來想如果dp[0]是false那整個遞推永遠啟動不了因為任何有效的拆分都要從下標0開始匹配第一個單詞。所以dp[0] true不是一個“業(yè)務(wù)上的真實拆法”它更像算法里的“哨兵值”或者叫占位符。你要是沒理解這一層后面在測試用例s 或者字典為空的時候很容易把代碼改錯。LeetCode的測試用例里雖然s是非空字符串但dp[0]這個位置在遞歸終止條件里也對應(yīng)著相同的概念統(tǒng)一處理最省心。2. 動態(tài)規(guī)劃核心推導(dǎo)從超時遞歸到dp[i]2.1 暴力回溯慢在哪指數(shù)級重復(fù)子問題先寫一個樸素回溯看看它慢在哪。偽代碼大概是這樣的boolean dfs(String s, int start, SetString dict) { if (start s.length()) return true; for (int end start 1; end s.length(); end) { if (dict.contains(s.substring(start, end)) dfs(s, end, dict)) { return true; } } return false; }這個寫法邏輯上完全正確但它存在大量重復(fù)計算。我拿s aaaaaaaaaaaaaaaaaaab字典是[a, aa, aaa, aaaa, ...]來舉例。從位置0開始匹配會先切a然后遞歸處理后面的字符串也會先切aa再遞歸處理后面的字符串。兩條路徑會在某個相同的下標處匯聚但每一條路徑都會把后續(xù)一整段重新計算一遍。如果你在遞歸函數(shù)里打印start的值會看到同一個start被調(diào)用了幾十次。這個重復(fù)量是指數(shù)級的所以提交超時一點都不冤。說白了dfs(7)這個狀態(tài)的結(jié)果不管你是通過切a到達第7位還是通過切aa或者aaa到達第7位計算出來的結(jié)果都是一樣的。它只跟“當前站在哪個位置”有關(guān)跟“怎么走到這個位置”無關(guān)。既然無關(guān)就應(yīng)該把它存下來——第一次算完存進緩存后面再遇到直接查表。這就是記憶化遞歸也是動態(tài)規(guī)劃最樸素的思想來源。2.2 狀態(tài)定義與轉(zhuǎn)移方程動態(tài)規(guī)劃要做的就是用一個數(shù)組dp把每個位置“從0能不能走到”存下來然后從前往后遞推。定義是這樣的dp[i]s的前i個字符也就是s[0:i]能不能被成功拆分成字典中的單詞。轉(zhuǎn)移方程寫成dp[i] true 當且僅當存在某個 j0 ≤ j i使得 dp[j] true 并且 s.substring(j, i) 在字典中。用大白話翻譯如果前j個字符已經(jīng)證明可以拆了而且從j到i這段剛好是一個字典里的單詞那我就可以把這段接上去于是前i個字符也能拆。這個“接上去”的動作是整個轉(zhuǎn)移方程的核心理解了這個代碼就是水到渠成的事。這里有一個很多人會寫錯的細節(jié)dp[i]是“前i個字符”能不能拆不是“下標i這個位置字符”能不能拆。下標i表示的是位置邊界而不是指向某個字符。比如s leetcodedp[4] true的意思是leet這四個字符可以拆并不表示s[4]這個字符是e還是什么。做字符串動態(tài)規(guī)劃的時候dp數(shù)組的下標和字符串的下標經(jīng)常錯半格這種“半格子”誤差是入門階段最經(jīng)典的bug來源排查的時候第一反應(yīng)就應(yīng)該檢查這里。2.3 遍歷順序、循環(huán)邊界與半格錯誤外層循環(huán)i從1到n表示逐步擴展前綴長度。為什么從1開始因為dp[0]是哨兵值已經(jīng)初始化好了真正要判斷的是從長度1的前綴開始一直判斷到整個字符串。內(nèi)層循環(huán)j從0到i-1枚舉所有可能的切割點。每到一個j就檢查兩件事第一dp[j]是不是true也就是前一段能不能拆第二從j到i這段子串在不在字典里。只要這兩個條件同時成立dp[i]就置為true并且可以直接break跳出內(nèi)層循環(huán)因為題目只問“能不能”不問“有哪些j能達成”。這一步剪枝能讓代碼在很多case下提前結(jié)束內(nèi)層循環(huán)省掉后面無意義的遍歷。寫代碼的時候還有個細節(jié)內(nèi)層j從0往i掃還是從i往0掃都不影響最終結(jié)果因為dp[i]的置true條件是“存在一個j”跟枚舉順序無關(guān)。不過如果你做了后面4.2節(jié)講的最小/最大長度剪枝建議j從可能范圍的兩端開始都行按習慣來就好。我自己習慣從0開始掃邏輯上更好解釋。3. 三種實現(xiàn)方案實測DP、記憶化遞歸、BFS3.1 自底向上的DP最穩(wěn)的寫法直接上Java的標準DP版本class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; for (int i 1; i n; i) { for (int j 0; j i; j) { if (dp[j] dict.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }這里有一個非常容易忽略但影響很大的點一定要先把List轉(zhuǎn)成HashSet再查不要直接用List.contains。因為List.contains是O(L)的線性查找HashSet.contains是O(1)的哈希查找。字典長度幾十個的時候沒感覺字典一長這個查詢成本直接乘進內(nèi)層循環(huán)里復(fù)雜度從理想狀態(tài)立刻惡化。我見過有人因為這一步從時間超限改到通過所以這個細節(jié)真不是小題大做。時間復(fù)雜度上最壞情況是O(n^2 * m)其中n是s的長度m可以理解為每次substring的拷貝開銷或者字典單詞平均長度。LeetCode這道題n不超過300這個復(fù)雜度完全夠用?？臻g復(fù)雜度是O(n)dp數(shù)組本身不大可以忽略。3.2 記憶化遞歸更貼近自然思維的版本如果你更習慣遞歸思維可以用memo記錄每個位置“從它開始能不能拆通”。我在本地對比過記憶化遞歸和自底向上的DP在時間復(fù)雜度上基本持平但它有個額外的好處遞歸天然只計算需要的狀態(tài)。如果某個分支提前返回true后面一大片狀態(tài)都不會被觸發(fā)在“答案很靠前”的case上會比DP更快。class Solution { private SetString dict; private MapInteger, Boolean memo; public boolean wordBreak(String s, ListString wordDict) { this.dict new HashSet(wordDict); this.memo new HashMap(); return dfs(s, 0); } private boolean dfs(String s, int start) { if (start s.length()) return true; if (memo.containsKey(start)) return memo.get(start); for (int end start 1; end s.length(); end) { if (dict.contains(s.substring(start, end)) dfs(s, end)) { memo.put(start, true); return true; } } memo.put(start, false); return false; } }這個寫法的遞歸深度最多是n1層s長度300的時候完全不用擔心爆棧。但要注意memo的鍵應(yīng)該是start不是end。我第一次寫的時候把memo鍵設(shè)成了end結(jié)果每個位置的狀態(tài)被拆得亂七八糟有的位置緩存了false有的位置緩存了true互相矛盾跑出來還是超時。核心認知是“從某個位置作為起點往后能不能拆通”這個狀態(tài)才有復(fù)用價值而終點end只是枚舉過程中的臨時變量。3.3 BFS視角把下標節(jié)點化成圖還有一派人喜歡把這道題理解成圖搜索字符串的每個下標都是一個節(jié)點每匹配上一個字典單詞就從當前下標連一條邊到“這個詞結(jié)束后的下一個位置”。目標是從下標0走到下標n這不就是圖上有向邊的可達性問題嘛。BFS代碼class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int n s.length(); boolean[] visited new boolean[n 1]; DequeInteger queue new ArrayDeque(); queue.offer(0); while (!queue.isEmpty()) { int start queue.poll(); if (start n) return true; if (visited[start]) continue; visited[start] true; for (int end start 1; end n; end) { if (dict.contains(s.substring(start, end))) { queue.offer(end); } } } return false; } }BFS和DP的區(qū)別在哪兒DP是嚴格按前綴長度從小到大遞推BFS是按“可達位置”一層層往外擴。在“答案很快就能找到”的時候BFS可能提前return true不用算完全部狀態(tài)但最壞情況下兩者的復(fù)雜度是一樣的。BFS有個額外風險某個位置可能被不同的路徑加入隊列好幾次所以visited數(shù)組不能省否則隊列會指數(shù)級膨脹。我實測過一個反例字典里全是a、aa、aaa這種前綴重疊的詞s又特別長不寫visited的BFS會重復(fù)入隊很多次直接內(nèi)存打滿。3.4 三份代碼的實測數(shù)據(jù)與選型建議我在LeetCode上分別提交過這三版代碼環(huán)境是Java 17s長度最大300字典單詞量大概是1000。三版都能通過耗時大多在3ms到15ms之間差異主要看數(shù)據(jù)形態(tài)。我做了一個小規(guī)模的對比可以作為參考方案實測耗時區(qū)間優(yōu)點缺點自底向上DP3~8ms代碼短、邏輯穩(wěn)、無遞歸棧風險狀態(tài)全部要算一遍不能提前終止記憶化遞歸2~10ms狀態(tài)定義直觀、可能提前返回遞歸深度受限制memo鍵寫錯就廢BFS2~15ms可提前找到答案、思路獨特需要visited防重復(fù)邏輯繞一些我的個人建議是面試里最好先講記憶化遞歸因為它的狀態(tài)定義最貼近人的自然思考方式講起來順講完再補一句“這里其實可以改成自底向上DP省掉遞歸棧代碼反而更穩(wěn)”這反而是個加分項。如果只求快速AC直接寫自底向上的DP它是三者里最好寫、最不容易出邏輯漏洞的版本。BFS適合作為思路拓展提一嘴展示你理解問題的角度比較多。4. 邊界與性能把容易超時的代碼救回來4.1 三個容易被忽略的性能細節(jié)先匯總一下我刷這道題時實際遇到過的坑每一個都是真實踩過的。第一個坑是substring的拷貝開銷。Java的substring會創(chuàng)建新字符串拷貝字符數(shù)組這個成本經(jīng)常被忽略。內(nèi)層循環(huán)里每次都要執(zhí)行substring(j, i)如果這一段在字典里還好說如果不在這次字符串創(chuàng)建就純屬浪費。尤其當i很大的時候前i個字符的子串要被反復(fù)創(chuàng)建很多次累加起來非?？捎^。第二個坑是內(nèi)層循環(huán)起點沒剪枝。很多人初始版本從j 0一直掃到i - 1但是在j很小、而s[j:i]的長度已經(jīng)遠遠超過字典里最長單詞長度的時候這段匹配注定失敗。字典里的單詞最長一般也就幾十個字符j離i越遠匹配成功的概率越低但substring還是白截了。這個坑在性能測試里最明顯。第三個坑是字典為空或者字典里沒有任何一個詞能匹配s的開頭。如果字典為空那不管s是什么答案都是false循環(huán)怎么跑都是false純屬空轉(zhuǎn)。雖然LeetCode測試用例不一定覆蓋這種情況但在本地做邊界測試時你的代碼要能扛住否則很尷尬。4.2 用最小/最大單詞長度剪枝最實用的一個優(yōu)化是維護字典單詞的最短長度minLen和最長長度maxLen。內(nèi)層循環(huán)里j的取值范圍就被限制在[i - maxLen, i - minLen]這個區(qū)間。意思是如果從j切到i的長度不在[minLen, maxLen]范圍內(nèi)那這段子串絕對不可能出現(xiàn)在字典里直接跳過即可。class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int minLen Integer.MAX_VALUE, maxLen 0; for (String w : wordDict) { minLen Math.min(minLen, w.length()); maxLen Math.max(maxLen, w.length()); } int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; for (int i 1; i n; i) { int left Math.max(0, i - maxLen); int right i - minLen; for (int j left; j right; j) { if (dp[j] dict.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }注意left可能等于0right可能小于0這時候內(nèi)層循環(huán)一次都不執(zhí)行dp[i]自然保持false這個處理是安全的。這個剪枝在特定數(shù)據(jù)下能把時間砍掉一半以上。比如s長度300字典里最短單詞長度1、最長單詞長度10內(nèi)層j的枚舉范圍最多10個位置復(fù)雜度從O(n^2)直接變成O(n * maxLen)。我實測下來從3ms降到0.3ms自己都有點意外。4.3 字典極大時的Trie優(yōu)化思路如果字典里有幾萬個單詞而且大量單詞共享前綴HashSet每次contains都要完整查一遍字符串比較浪費。這時候可以考慮Trie前綴樹。把字典所有單詞插入Trie在內(nèi)層循環(huán)里用Trie去匹配s.substring(j, i)。匹配過程中一旦遇到Trie里沒有的字符路徑直接終止這輪匹配就可以快速排除大量不可能的切分點。等于把“從一個起點出發(fā)枚舉所有可能的end”這個動作交給Trie來驅(qū)動避免了很多無效的子串比較。不過說實話LeetCode 139這道題本身的數(shù)據(jù)規(guī)模不需要TrieTrie主要用在LeetCode 140或者“字典單詞數(shù)量極大”的場景里。面試時可以主動提一句“如果字典特別大我會考慮用Trie來加速匹配”但我不建議一上來就寫Trie因為代碼復(fù)雜度高、容易寫錯而且在這個數(shù)據(jù)范圍下收益不明顯。面試官想聽到的關(guān)鍵是“你知道有這條優(yōu)化路徑”而不是非要在題目里實現(xiàn)才算完。5. 這道題的實戰(zhàn)價值與面試進階路徑5.1 業(yè)務(wù)中的“單詞拆分”模式很多初學者覺得動態(tài)規(guī)劃刷完就完了跟真實業(yè)務(wù)沒什么關(guān)系。但“單詞拆分”這個模式在工程界其實非常常見。用一個不太嚴謹?shù)苜N切的描述它本質(zhì)上是“給定一個被拼接起來的字符串判斷它能不能被已知的模式集合切分成合法單元”。最典型的應(yīng)用是中文分詞。分詞器拿到一段沒有空格的中文文本內(nèi)部維護了一個詞典本質(zhì)上就是要把文本切分成詞典里的詞只是它還涉及歧義消解和未登錄詞處理。英文里也有同樣的問題比如OCR識別結(jié)果的糾錯、拼音輸入法的候選生成都會用到類似的動態(tài)規(guī)劃切分思想。另一個更接地氣的場景是敏感詞過濾。假設(shè)系統(tǒng)維護了一批敏感詞現(xiàn)在有一段用戶輸入需要判斷這段輸入是否可以拆分成若干片段其中任何一個片段命中敏感詞就報警。這就是單詞拆分模式的一個變體。還有URL的路由匹配把路徑拆成多段再逐段匹配路由規(guī)則也有點這個意思。我自己寫日志解析工具的時候也踩過類似的邏輯一行日志每行前面有固定格式的字段后面是消息體要快速判斷一行日志能不能按既定格式解析本質(zhì)上就是“前綴序列是否完整可匹配”的問題跟dp[i]的思路一模一樣。5.2 兩個必須會的變體140和132LeetCode 139的兩個經(jīng)典變體面試里非常容易遇到值得一起刷。第一個是LeetCode 140不僅要判斷能不能拆還要返回所有可行的拆分方案。這時候判定問題的dp就退位了得改用記憶化搜索回溯從后往前記錄每個位置往后能構(gòu)成哪些完整句子。難點在于“同一個位置可能有多種拆法”dp只保留true/false是不夠的需要存一個從位置到“后續(xù)所有句子集合”的映射。理解了139的狀態(tài)設(shè)計140就只是給狀態(tài)加了更多信息而已。第二個是LeetCode 132最少切割次數(shù)把字符串切成若干回文子串所需的最小切割次數(shù)。雖然它考的是回文不是字典但狀態(tài)定義邏輯幾乎一脈相承dp[i]表示前i個字符需要的最少切割次數(shù)再用一個isPal[i][j]預(yù)存子串是否回文。理解了139的狀態(tài)設(shè)計132就是換個cost維度的事核心動態(tài)規(guī)劃骨架完全一樣。我把這兩道題跟139放在一起刷字符串動態(tài)規(guī)劃立刻通透了不少。還有一道LinkedIn考過的變體字典里的單詞可以重復(fù)使用但順序要匹配問s能不能被拆成字典里某個單詞的無限重復(fù)序列。本質(zhì)上就是“判斷s是否形如某個單詞的重復(fù)”處理起來更簡單。把這類變體都過一遍你會發(fā)現(xiàn)139吃透之后字符串動態(tài)規(guī)劃題基本都通了。5.3 面試講題節(jié)奏與貪心反例如果面試官讓你講這道題我建議按這個節(jié)奏回答。第一層先說明這是一個判定問題目標是判斷可行性而不是列舉方案所以優(yōu)先想動態(tài)規(guī)劃而不是回溯。第二層講清楚狀態(tài)定義dp[i]和轉(zhuǎn)移方程dp[i] 存在j讓dp[j] s[j:i]在字典里同時主動解釋為什么dp[0] true體現(xiàn)你真的理解“哨兵值”而不是在背模板。第三層講復(fù)雜度時間O(n^2 * m)、空間O(n)這里要主動提到HashSet換成List.contains的問題。第四層講優(yōu)化內(nèi)層循環(huán)剪枝、最小最大長度限制、極端大字典上Trie面試官如果追問能答到Trie就已經(jīng)超過大部分候選人了。還有一個肯定會被問到的問題為什么不能用貪心我見過有人回答“因為貪心不一定對”就沒下文了被追問“能不能舉個反例”直接卡住。你要能舉出catsandog這個例子貪心先切cat后面sandog就死了但如果先看sand后面og又不行。這個反例在腦子里要常備隨時能講出來而不是臨時想。我在實際刷題中最大的體會是139這道題特別適合用來驗證自己到底懂不懂動態(tài)規(guī)劃。它不像背包問題那樣有固定的物品維度也不像最長公共子序列那樣有兩個字符串它就是一個純字符串上的分段判定把“無后效性”“哨兵值”“剪枝”這些概念全部過了一遍。把這道題弄明白再去看后面那些字符串動態(tài)規(guī)劃的題你會覺得它們都像是同一個骨架換了一層皮。這也是為什么它在LeetCode熱門100題里地位那么穩(wěn)的原因。 LeetCode 139單詞拆分：從遞歸到動態(tài)規(guī)劃的完整推導(dǎo)與優(yōu)化
前幾天在群里看到有人問LeetCode 139這道單詞拆分說自己花了大半小時寫了套遞歸樣例全過一提交就超時。這問題我太有共鳴了——當年我刷LeetCode 139單詞拆分的時候同樣在“怎么把遞歸改成動態(tài)規(guī)劃”這一步卡了兩天。今天這篇不想只貼一份標準答案糊弄人我想把這道題從暴力遞歸到動態(tài)規(guī)劃再到BFS的完整推導(dǎo)過程、邊界條件、還有我實測下來踩過的性能坑一次性講清楚。如果你正在刷LeetCode熱門100題或者準備面試時遇到字符串相關(guān)的動態(tài)規(guī)劃題目這篇應(yīng)該能幫你省下不少彎路。1. 題目拆解讀懂“可拆分”到底在問什么1.1 三個樣例分別埋了哪些坑LeetCode 139給的標準樣例其實埋了三個層次的陷阱我一個個拆開說。第一個樣例s leetcode字典 [leet, code]返回 true。這是最簡單的線性拆分從前往后切一刀就行對應(yīng)到代碼里就是“s[0:4]在字典里s[4:8]也在字典里”。這里唯一要注意的是Java中substring是左閉右開substring(0, 4)取到的是leetsubstring(4, 8)取到的是code。這個邊界問題寫錯的人特別多尤其是從C轉(zhuǎn)過來的同學習慣了左閉右開還好第一次寫Java的時候很容易把endIndex寫成4。第二個樣例s applepenapple字典 [apple, pen]返回 true。這個樣例想說的關(guān)鍵信息是同一個單詞可以在拆分結(jié)果里重復(fù)出現(xiàn)。也就是說字典里的每個單詞使用次數(shù)沒有限制你可以無窮次地使用它只要最后拼出來的字符串等于s就行。這一點非常重要因為它直接決定了我們不需要在狀態(tài)里記錄“哪個單詞用過了”——這是很多人在思考時被卡住的地方。第三個樣例s catsandog字典 [cats, dog, sand, and, cat]返回 false。這個樣例是專門用來坑人的從cats開始拆可以拆出cats、and、og但og不在字典里從cat開始拆后面是sandog怎么切都切不像。它想表達的是局部匹配成功不代表整體能成功你沒法用貪心算法從頭掃到尾取一個能匹配的就完事。這個反例后面面試講題時經(jīng)常被追問最好背下來。1.2 判定問題先于方案列舉我在帶人刷題的時候發(fā)現(xiàn)一個規(guī)律凡是第一次看到這道題能直接寫對的人基本都是先意識到了它是一個判定問題。題目問的是“能不能被拆分成若干個單詞”不是“有幾種拆分方式”更不是“把每一種拆分方式都列出來”。這個區(qū)別決定了算法走向判定問題可以只保留“行/不行”這個布爾信息把中途所有詳細的拆分過程全部扔掉。舉個例子假設(shè)你正站在第j個字符的位置前面已經(jīng)拆到這兒了你不需要關(guān)心前面具體是被拆成了[leet,co]還是[le,etc,od]——你只需要知道“能不能拆到第j個字符”這一個事實。一旦這個事實確定了后面怎么拆就只跟當前下標j有關(guān)跟之前的路徑完全無關(guān)。這就是動態(tài)規(guī)劃很喜歡講的“無后效性”也是這道題能從指數(shù)級的暴力枚舉優(yōu)化到多項式時間的關(guān)鍵。很多新手在這里會糾結(jié)如果前面的具體拆分方式不同后面能匹配的單詞會不會不同答案是不會。因為字典匹配只看從j開始的那段子串不關(guān)心j之前的內(nèi)容是什么。這個思維轉(zhuǎn)換是字符串動態(tài)規(guī)劃題目的通用判斷標準不光139用得上132、140那一類題都靠這個邏輯。1.3 一個容易翻車的邊界dp[0]哨兵值幾乎所有題解都會直接說dp[0] true但很少有人解釋為什么。我的理解是一個空前綴本身不需要拆分它天然是“可選起點”。你可以把任何一次成功的拆分看作“從前一個位置出發(fā)拼了某個單詞”而起始位置0要能出發(fā)就得先有一個dp[0] true作為起點。反過來想如果dp[0]是false那整個遞推永遠啟動不了因為任何有效的拆分都要從下標0開始匹配第一個單詞。所以dp[0] true不是一個“業(yè)務(wù)上的真實拆法”它更像算法里的“哨兵值”或者叫占位符。你要是沒理解這一層后面在測試用例s 或者字典為空的時候很容易把代碼改錯。LeetCode的測試用例里雖然s是非空字符串但dp[0]這個位置在遞歸終止條件里也對應(yīng)著相同的概念統(tǒng)一處理最省心。2. 動態(tài)規(guī)劃核心推導(dǎo)從超時遞歸到dp[i]2.1 暴力回溯慢在哪指數(shù)級重復(fù)子問題先寫一個樸素回溯看看它慢在哪。偽代碼大概是這樣的boolean dfs(String s, int start, SetString dict) { if (start s.length()) return true; for (int end start 1; end s.length(); end) { if (dict.contains(s.substring(start, end)) dfs(s, end, dict)) { return true; } } return false; }這個寫法邏輯上完全正確但它存在大量重復(fù)計算。我拿s aaaaaaaaaaaaaaaaaaab字典是[a, aa, aaa, aaaa, ...]來舉例。從位置0開始匹配會先切a然后遞歸處理后面的字符串也會先切aa再遞歸處理后面的字符串。兩條路徑會在某個相同的下標處匯聚但每一條路徑都會把后續(xù)一整段重新計算一遍。如果你在遞歸函數(shù)里打印start的值會看到同一個start被調(diào)用了幾十次。這個重復(fù)量是指數(shù)級的所以提交超時一點都不冤。說白了dfs(7)這個狀態(tài)的結(jié)果不管你是通過切a到達第7位還是通過切aa或者aaa到達第7位計算出來的結(jié)果都是一樣的。它只跟“當前站在哪個位置”有關(guān)跟“怎么走到這個位置”無關(guān)。既然無關(guān)就應(yīng)該把它存下來——第一次算完存進緩存后面再遇到直接查表。這就是記憶化遞歸也是動態(tài)規(guī)劃最樸素的思想來源。2.2 狀態(tài)定義與轉(zhuǎn)移方程動態(tài)規(guī)劃要做的就是用一個數(shù)組dp把每個位置“從0能不能走到”存下來然后從前往后遞推。定義是這樣的dp[i]s的前i個字符也就是s[0:i]能不能被成功拆分成字典中的單詞。轉(zhuǎn)移方程寫成dp[i] true 當且僅當存在某個 j0 ≤ j i使得 dp[j] true 并且 s.substring(j, i) 在字典中。用大白話翻譯如果前j個字符已經(jīng)證明可以拆了而且從j到i這段剛好是一個字典里的單詞那我就可以把這段接上去于是前i個字符也能拆。這個“接上去”的動作是整個轉(zhuǎn)移方程的核心理解了這個代碼就是水到渠成的事。這里有一個很多人會寫錯的細節(jié)dp[i]是“前i個字符”能不能拆不是“下標i這個位置字符”能不能拆。下標i表示的是位置邊界而不是指向某個字符。比如s leetcodedp[4] true的意思是leet這四個字符可以拆并不表示s[4]這個字符是e還是什么。做字符串動態(tài)規(guī)劃的時候dp數(shù)組的下標和字符串的下標經(jīng)常錯半格這種“半格子”誤差是入門階段最經(jīng)典的bug來源排查的時候第一反應(yīng)就應(yīng)該檢查這里。2.3 遍歷順序、循環(huán)邊界與半格錯誤外層循環(huán)i從1到n表示逐步擴展前綴長度。為什么從1開始因為dp[0]是哨兵值已經(jīng)初始化好了真正要判斷的是從長度1的前綴開始一直判斷到整個字符串。內(nèi)層循環(huán)j從0到i-1枚舉所有可能的切割點。每到一個j就檢查兩件事第一dp[j]是不是true也就是前一段能不能拆第二從j到i這段子串在不在字典里。只要這兩個條件同時成立dp[i]就置為true并且可以直接break跳出內(nèi)層循環(huán)因為題目只問“能不能”不問“有哪些j能達成”。這一步剪枝能讓代碼在很多case下提前結(jié)束內(nèi)層循環(huán)省掉后面無意義的遍歷。寫代碼的時候還有個細節(jié)內(nèi)層j從0往i掃還是從i往0掃都不影響最終結(jié)果因為dp[i]的置true條件是“存在一個j”跟枚舉順序無關(guān)。不過如果你做了后面4.2節(jié)講的最小/最大長度剪枝建議j從可能范圍的兩端開始都行按習慣來就好。我自己習慣從0開始掃邏輯上更好解釋。3. 三種實現(xiàn)方案實測DP、記憶化遞歸、BFS3.1 自底向上的DP最穩(wěn)的寫法直接上Java的標準DP版本class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; for (int i 1; i n; i) { for (int j 0; j i; j) { if (dp[j] dict.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }這里有一個非常容易忽略但影響很大的點一定要先把List轉(zhuǎn)成HashSet再查不要直接用List.contains。因為List.contains是O(L)的線性查找HashSet.contains是O(1)的哈希查找。字典長度幾十個的時候沒感覺字典一長這個查詢成本直接乘進內(nèi)層循環(huán)里復(fù)雜度從理想狀態(tài)立刻惡化。我見過有人因為這一步從時間超限改到通過所以這個細節(jié)真不是小題大做。時間復(fù)雜度上最壞情況是O(n^2 * m)其中n是s的長度m可以理解為每次substring的拷貝開銷或者字典單詞平均長度。LeetCode這道題n不超過300這個復(fù)雜度完全夠用?？臻g復(fù)雜度是O(n)dp數(shù)組本身不大可以忽略。3.2 記憶化遞歸更貼近自然思維的版本如果你更習慣遞歸思維可以用memo記錄每個位置“從它開始能不能拆通”。我在本地對比過記憶化遞歸和自底向上的DP在時間復(fù)雜度上基本持平但它有個額外的好處遞歸天然只計算需要的狀態(tài)。如果某個分支提前返回true后面一大片狀態(tài)都不會被觸發(fā)在“答案很靠前”的case上會比DP更快。class Solution { private SetString dict; private MapInteger, Boolean memo; public boolean wordBreak(String s, ListString wordDict) { this.dict new HashSet(wordDict); this.memo new HashMap(); return dfs(s, 0); } private boolean dfs(String s, int start) { if (start s.length()) return true; if (memo.containsKey(start)) return memo.get(start); for (int end start 1; end s.length(); end) { if (dict.contains(s.substring(start, end)) dfs(s, end)) { memo.put(start, true); return true; } } memo.put(start, false); return false; } }這個寫法的遞歸深度最多是n1層s長度300的時候完全不用擔心爆棧。但要注意memo的鍵應(yīng)該是start不是end。我第一次寫的時候把memo鍵設(shè)成了end結(jié)果每個位置的狀態(tài)被拆得亂七八糟有的位置緩存了false有的位置緩存了true互相矛盾跑出來還是超時。核心認知是“從某個位置作為起點往后能不能拆通”這個狀態(tài)才有復(fù)用價值而終點end只是枚舉過程中的臨時變量。3.3 BFS視角把下標節(jié)點化成圖還有一派人喜歡把這道題理解成圖搜索字符串的每個下標都是一個節(jié)點每匹配上一個字典單詞就從當前下標連一條邊到“這個詞結(jié)束后的下一個位置”。目標是從下標0走到下標n這不就是圖上有向邊的可達性問題嘛。BFS代碼class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int n s.length(); boolean[] visited new boolean[n 1]; DequeInteger queue new ArrayDeque(); queue.offer(0); while (!queue.isEmpty()) { int start queue.poll(); if (start n) return true; if (visited[start]) continue; visited[start] true; for (int end start 1; end n; end) { if (dict.contains(s.substring(start, end))) { queue.offer(end); } } } return false; } }BFS和DP的區(qū)別在哪兒DP是嚴格按前綴長度從小到大遞推BFS是按“可達位置”一層層往外擴。在“答案很快就能找到”的時候BFS可能提前return true不用算完全部狀態(tài)但最壞情況下兩者的復(fù)雜度是一樣的。BFS有個額外風險某個位置可能被不同的路徑加入隊列好幾次所以visited數(shù)組不能省否則隊列會指數(shù)級膨脹。我實測過一個反例字典里全是a、aa、aaa這種前綴重疊的詞s又特別長不寫visited的BFS會重復(fù)入隊很多次直接內(nèi)存打滿。3.4 三份代碼的實測數(shù)據(jù)與選型建議我在LeetCode上分別提交過這三版代碼環(huán)境是Java 17s長度最大300字典單詞量大概是1000。三版都能通過耗時大多在3ms到15ms之間差異主要看數(shù)據(jù)形態(tài)。我做了一個小規(guī)模的對比可以作為參考方案實測耗時區(qū)間優(yōu)點缺點自底向上DP3~8ms代碼短、邏輯穩(wěn)、無遞歸棧風險狀態(tài)全部要算一遍不能提前終止記憶化遞歸2~10ms狀態(tài)定義直觀、可能提前返回遞歸深度受限制memo鍵寫錯就廢BFS2~15ms可提前找到答案、思路獨特需要visited防重復(fù)邏輯繞一些我的個人建議是面試里最好先講記憶化遞歸因為它的狀態(tài)定義最貼近人的自然思考方式講起來順講完再補一句“這里其實可以改成自底向上DP省掉遞歸棧代碼反而更穩(wěn)”這反而是個加分項。如果只求快速AC直接寫自底向上的DP它是三者里最好寫、最不容易出邏輯漏洞的版本。BFS適合作為思路拓展提一嘴展示你理解問題的角度比較多。4. 邊界與性能把容易超時的代碼救回來4.1 三個容易被忽略的性能細節(jié)先匯總一下我刷這道題時實際遇到過的坑每一個都是真實踩過的。第一個坑是substring的拷貝開銷。Java的substring會創(chuàng)建新字符串拷貝字符數(shù)組這個成本經(jīng)常被忽略。內(nèi)層循環(huán)里每次都要執(zhí)行substring(j, i)如果這一段在字典里還好說如果不在這次字符串創(chuàng)建就純屬浪費。尤其當i很大的時候前i個字符的子串要被反復(fù)創(chuàng)建很多次累加起來非?？捎^。第二個坑是內(nèi)層循環(huán)起點沒剪枝。很多人初始版本從j 0一直掃到i - 1但是在j很小、而s[j:i]的長度已經(jīng)遠遠超過字典里最長單詞長度的時候這段匹配注定失敗。字典里的單詞最長一般也就幾十個字符j離i越遠匹配成功的概率越低但substring還是白截了。這個坑在性能測試里最明顯。第三個坑是字典為空或者字典里沒有任何一個詞能匹配s的開頭。如果字典為空那不管s是什么答案都是false循環(huán)怎么跑都是false純屬空轉(zhuǎn)。雖然LeetCode測試用例不一定覆蓋這種情況但在本地做邊界測試時你的代碼要能扛住否則很尷尬。4.2 用最小/最大單詞長度剪枝最實用的一個優(yōu)化是維護字典單詞的最短長度minLen和最長長度maxLen。內(nèi)層循環(huán)里j的取值范圍就被限制在[i - maxLen, i - minLen]這個區(qū)間。意思是如果從j切到i的長度不在[minLen, maxLen]范圍內(nèi)那這段子串絕對不可能出現(xiàn)在字典里直接跳過即可。class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString dict new HashSet(wordDict); int minLen Integer.MAX_VALUE, maxLen 0; for (String w : wordDict) { minLen Math.min(minLen, w.length()); maxLen Math.max(maxLen, w.length()); } int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; for (int i 1; i n; i) { int left Math.max(0, i - maxLen); int right i - minLen; for (int j left; j right; j) { if (dp[j] dict.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }注意left可能等于0right可能小于0這時候內(nèi)層循環(huán)一次都不執(zhí)行dp[i]自然保持false這個處理是安全的。這個剪枝在特定數(shù)據(jù)下能把時間砍掉一半以上。比如s長度300字典里最短單詞長度1、最長單詞長度10內(nèi)層j的枚舉范圍最多10個位置復(fù)雜度從O(n^2)直接變成O(n * maxLen)。我實測下來從3ms降到0.3ms自己都有點意外。4.3 字典極大時的Trie優(yōu)化思路如果字典里有幾萬個單詞而且大量單詞共享前綴HashSet每次contains都要完整查一遍字符串比較浪費。這時候可以考慮Trie前綴樹。把字典所有單詞插入Trie在內(nèi)層循環(huán)里用Trie去匹配s.substring(j, i)。匹配過程中一旦遇到Trie里沒有的字符路徑直接終止這輪匹配就可以快速排除大量不可能的切分點。等于把“從一個起點出發(fā)枚舉所有可能的end”這個動作交給Trie來驅(qū)動避免了很多無效的子串比較。不過說實話LeetCode 139這道題本身的數(shù)據(jù)規(guī)模不需要TrieTrie主要用在LeetCode 140或者“字典單詞數(shù)量極大”的場景里。面試時可以主動提一句“如果字典特別大我會考慮用Trie來加速匹配”但我不建議一上來就寫Trie因為代碼復(fù)雜度高、容易寫錯而且在這個數(shù)據(jù)范圍下收益不明顯。面試官想聽到的關(guān)鍵是“你知道有這條優(yōu)化路徑”而不是非要在題目里實現(xiàn)才算完。5. 這道題的實戰(zhàn)價值與面試進階路徑5.1 業(yè)務(wù)中的“單詞拆分”模式很多初學者覺得動態(tài)規(guī)劃刷完就完了跟真實業(yè)務(wù)沒什么關(guān)系。但“單詞拆分”這個模式在工程界其實非常常見。用一個不太嚴謹?shù)苜N切的描述它本質(zhì)上是“給定一個被拼接起來的字符串判斷它能不能被已知的模式集合切分成合法單元”。最典型的應(yīng)用是中文分詞。分詞器拿到一段沒有空格的中文文本內(nèi)部維護了一個詞典本質(zhì)上就是要把文本切分成詞典里的詞只是它還涉及歧義消解和未登錄詞處理。英文里也有同樣的問題比如OCR識別結(jié)果的糾錯、拼音輸入法的候選生成都會用到類似的動態(tài)規(guī)劃切分思想。另一個更接地氣的場景是敏感詞過濾。假設(shè)系統(tǒng)維護了一批敏感詞現(xiàn)在有一段用戶輸入需要判斷這段輸入是否可以拆分成若干片段其中任何一個片段命中敏感詞就報警。這就是單詞拆分模式的一個變體。還有URL的路由匹配把路徑拆成多段再逐段匹配路由規(guī)則也有點這個意思。我自己寫日志解析工具的時候也踩過類似的邏輯一行日志每行前面有固定格式的字段后面是消息體要快速判斷一行日志能不能按既定格式解析本質(zhì)上就是“前綴序列是否完整可匹配”的問題跟dp[i]的思路一模一樣。5.2 兩個必須會的變體140和132LeetCode 139的兩個經(jīng)典變體面試里非常容易遇到值得一起刷。第一個是LeetCode 140不僅要判斷能不能拆還要返回所有可行的拆分方案。這時候判定問題的dp就退位了得改用記憶化搜索回溯從后往前記錄每個位置往后能構(gòu)成哪些完整句子。難點在于“同一個位置可能有多種拆法”dp只保留true/false是不夠的需要存一個從位置到“后續(xù)所有句子集合”的映射。理解了139的狀態(tài)設(shè)計140就只是給狀態(tài)加了更多信息而已。第二個是LeetCode 132最少切割次數(shù)把字符串切成若干回文子串所需的最小切割次數(shù)。雖然它考的是回文不是字典但狀態(tài)定義邏輯幾乎一脈相承dp[i]表示前i個字符需要的最少切割次數(shù)再用一個isPal[i][j]預(yù)存子串是否回文。理解了139的狀態(tài)設(shè)計132就是換個cost維度的事核心動態(tài)規(guī)劃骨架完全一樣。我把這兩道題跟139放在一起刷字符串動態(tài)規(guī)劃立刻通透了不少。還有一道LinkedIn考過的變體字典里的單詞可以重復(fù)使用但順序要匹配問s能不能被拆成字典里某個單詞的無限重復(fù)序列。本質(zhì)上就是“判斷s是否形如某個單詞的重復(fù)”處理起來更簡單。把這類變體都過一遍你會發(fā)現(xiàn)139吃透之后字符串動態(tài)規(guī)劃題基本都通了。5.3 面試講題節(jié)奏與貪心反例如果面試官讓你講這道題我建議按這個節(jié)奏回答。第一層先說明這是一個判定問題目標是判斷可行性而不是列舉方案所以優(yōu)先想動態(tài)規(guī)劃而不是回溯。第二層講清楚狀態(tài)定義dp[i]和轉(zhuǎn)移方程dp[i] 存在j讓dp[j] s[j:i]在字典里同時主動解釋為什么dp[0] true體現(xiàn)你真的理解“哨兵值”而不是在背模板。第三層講復(fù)雜度時間O(n^2 * m)、空間O(n)這里要主動提到HashSet換成List.contains的問題。第四層講優(yōu)化內(nèi)層循環(huán)剪枝、最小最大長度限制、極端大字典上Trie面試官如果追問能答到Trie就已經(jīng)超過大部分候選人了。還有一個肯定會被問到的問題為什么不能用貪心我見過有人回答“因為貪心不一定對”就沒下文了被追問“能不能舉個反例”直接卡住。你要能舉出catsandog這個例子貪心先切cat后面sandog就死了但如果先看sand后面og又不行。這個反例在腦子里要常備隨時能講出來而不是臨時想。我在實際刷題中最大的體會是139這道題特別適合用來驗證自己到底懂不懂動態(tài)規(guī)劃。它不像背包問題那樣有固定的物品維度也不像最長公共子序列那樣有兩個字符串它就是一個純字符串上的分段判定把“無后效性”“哨兵值”“剪枝”這些概念全部過了一遍。把這道題弄明白再去看后面那些字符串動態(tài)規(guī)劃的題你會覺得它們都像是同一個骨架換了一層皮。這也是為什么它在LeetCode熱門100題里地位那么穩(wěn)的原因。