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