 復(fù)雜度全解)
LeetCode 131 回文分割Palindrome Partitioning回溯 雙索引遞歸與 O(n·2^n) 復(fù)雜度全解【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南以 hints/palindrome-partitioning.md 給出的解題提示為核心骨架系統(tǒng)講解 LeetCode 131「分割回文串」的完整解法從「為什么存在 2^n 種切分」的復(fù)雜度直覺(jué)出發(fā)逐步推導(dǎo)出雙索引回溯j 為當(dāng)前子串起點(diǎn)、i 為擴(kuò)展終點(diǎn)、按起點(diǎn)枚舉的回溯、DP 預(yù)計(jì)算回文表與純遞歸返回式四種實(shí)現(xiàn)并結(jié)合本倉(cāng)庫(kù)多語(yǔ)言源碼逐一印證。讀完你將掌握回文分割問(wèn)題的標(biāo)準(zhǔn)思考路徑、可直接運(yùn)行的代碼模板以及一份能寫(xiě)進(jìn)面試的復(fù)雜度分析。1. 問(wèn)題定義與目標(biāo)復(fù)雜度題目要求給定字符串s將s分割成若干子串使得每一個(gè)子串都是回文串返回所有可能的分割方案。例如s aab的輸出為[[a,a,b], [aa,b]]s a的輸出為[[a]]。提示文檔在開(kāi)篇即給出了本問(wèn)題的推薦復(fù)雜度目標(biāo)目標(biāo)解法應(yīng)達(dá)到O(n * 2^n)時(shí)間、O(n)空間其中n為輸入字符串長(zhǎng)度。這一目標(biāo)直接決定了算法形態(tài)由于答案數(shù)量本身是指數(shù)級(jí)的見(jiàn)下一節(jié)任何解法的下界都跑不出O(2^n)量級(jí)因此回溯Backtracking 剪枝就是最匹配的范式——它天然適合枚舉所有組合又通過(guò)「只接納回文子串」完成剪枝。倉(cāng)庫(kù)中的 cpp/0131-palindrome-partitioning.cpp 頭注釋也明確標(biāo)注了Time: O(n x 2^n)、Space: O(n)與提示文檔完全一致。2. 為什么有 2^n 種切分Hint 1 的復(fù)雜度直覺(jué)提示文檔的 Hint 1 給出了一個(gè)關(guān)鍵觀察對(duì)給定字符串存在2^n 種可能的切分因?yàn)樵诿總€(gè)索引處都有兩個(gè)決策要么在此處切分并開(kāi)始一個(gè)新的子串要么不切分繼續(xù)延伸當(dāng)前子串。理解這個(gè)結(jié)論是理解算法結(jié)構(gòu)的鑰匙。想象在字符串的n-1個(gè)相鄰字符之間放置「切/不切」的決策點(diǎn)切 → 當(dāng)前子串結(jié)束從下一位置開(kāi)啟新子串不切 → 當(dāng)前子串繼續(xù)向右延伸。每個(gè)位置兩個(gè)選擇組合起來(lái)恰好構(gòu)成一棵2^n 規(guī)模的決策樹(shù)?；厮菟惴ū举|(zhì)上就是遞歸遍歷這棵決策樹(shù)樹(shù)的高度為n字符串被逐字符消費(fèi)每一條從根到葉的路徑對(duì)應(yīng)一種切分方式其中「每個(gè)子串都是回文」的路徑才被采納進(jìn)結(jié)果。因此答案集最壞情況下有O(2^n)個(gè)方案每個(gè)方案平均長(zhǎng)度O(n)加上對(duì)每個(gè)方案做回文校驗(yàn)的開(kāi)銷(xiāo)總時(shí)間復(fù)雜度定格在O(n * 2^n)——這正是推薦復(fù)雜度目標(biāo)的時(shí)間來(lái)源。3. 雙索引回溯j, i對(duì)應(yīng) Hint 2 與 Hint 3 的核心實(shí)現(xiàn)3.1 指針含義與狀態(tài)設(shè)計(jì)提示文檔的 Hint 2 定義了本題最精煉的雙指針狀態(tài)j當(dāng)前待構(gòu)造子串的起始索引i當(dāng)前正在迭代擴(kuò)展的索引即子串的候選終點(diǎn)。每一步迭代中只有兩類(lèi)決策暫不切分保持j不變把i向右推進(jìn)一位dfs(j, i1)嘗試更長(zhǎng)的子串切分當(dāng)s[j..i]是回文時(shí)把該子串放入臨時(shí)列表part隨后令j i 1開(kāi)啟新的子串并從新起點(diǎn)繼續(xù)遞歸dfs(i1, i1)。遞歸的終止條件Hint 2 強(qiáng)調(diào)當(dāng)j走到字符串末尾時(shí)停止——這表示從起點(diǎn)到末尾的每一段都已被成功切分成回文當(dāng)前part即為一個(gè)合法答案。3.2 代碼模板PythonHint 3 補(bǔ)充了初始化細(xì)節(jié)從j 0, i 0和一個(gè)空的臨時(shí)列表part出發(fā)到達(dá)基礎(chǔ)條件時(shí)把part的拷貝加入結(jié)果集。據(jù)此得到的實(shí)現(xiàn)如下class Solution: def partition(self, s: str) - List[List[str]]: res, part [], [] def dfs(j, i): if i len(s): if i j: # 恰好完整切分完整個(gè)字符串 res.append(part.copy()) return if self.isPali(s, j, i): # 決策 2s[j..i] 是回文 → 切分 part.append(s[j : i 1]) dfs(i 1, i 1) # 新子串從 i1 開(kāi)始 part.pop() # 回溯撤銷(xiāo)選擇 dfs(j, i 1) # 決策 1不切分繼續(xù)延伸 dfs(0, 0) return res def isPali(self, s, l, r): while l r: if s[l] ! s[r]: return False l, r l 1, r - 1 return True注意兩個(gè)容易被忽略的細(xì)節(jié)基礎(chǔ)條件的雙重判斷i len(s)時(shí)只有i j才意味著「當(dāng)前子串恰好延伸到末尾且被完整消費(fèi)」此時(shí)part才是合法答案若i j說(shuō)明最后一串尚未確定是否為回文直接返回不收集?；匚呐卸╥sPali用雙指針向中間收縮l與r一旦出現(xiàn)字符不等立即返回False最壞O(n)這是 Hint 2 中明確要求的校驗(yàn)方式。3.3 該寫(xiě)法的復(fù)雜度時(shí)間O(n * 2^n)—— 枚舉全部切分組合每層做O(n)的回文校驗(yàn)空間O(n)額外空間遞歸棧深度 part列表不包含答案輸出本身占用的O(n * 2^n)。與 articles/palindrome-partitioning.md 中「Backtracking - I」一節(jié)的結(jié)論完全一致。4. 按起點(diǎn)枚舉的回溯倉(cāng)庫(kù)源碼的權(quán)威實(shí)現(xiàn)除雙索引寫(xiě)法外更常見(jiàn)、也更貼近本倉(cāng)庫(kù)實(shí)際提交的是按起點(diǎn)枚舉的回溯定義dfs(i)i是下一個(gè)子串的起點(diǎn)在i..n-1范圍內(nèi)枚舉終點(diǎn)j只要s[i..j]是回文就選取它并遞歸處理j1之后的剩余部分返回后pop撤銷(xiāo)?；A(chǔ)條件是i len(s)時(shí)把part的拷貝收入結(jié)果。倉(cāng)庫(kù)中的 python/0131-palindrome-partitioning.py 正是這一形態(tài)的完整實(shí)現(xiàn)class Solution: def partition(self, s: str) - List[List[str]]: res, part [], [] def dfs(i): if i len(s): res.append(part.copy()) return for j in range(i, len(s)): if self.isPali(s, i, j): part.append(s[i : j 1]) dfs(j 1) part.pop() dfs(0) return res def isPali(self, s, l, r): while l r: if s[l] ! s[r]: return False l, r l 1, r - 1 return True該解法與雙索引寫(xiě)法在決策語(yǔ)義上等價(jià)雙索引寫(xiě)法的「切分決策 不切分延伸」展開(kāi)后恰好覆蓋了按起點(diǎn)枚舉中「以i為起點(diǎn)、終點(diǎn)j從i掃到n-1」的全部子串區(qū)別僅在于狀態(tài)組織方式。按起點(diǎn)枚舉版更簡(jiǎn)潔是面試中最推薦的表達(dá)。同目錄下的多語(yǔ)言實(shí)現(xiàn)結(jié)構(gòu)一致可對(duì)照閱讀cpp/0131-palindrome-partitioning.cppdfs(s, start, curr, result)以start s.size()為終止條件isPalindrome雙指針校驗(yàn)go/0131-palindrome-partitioning.go用閉包backtrack(idx)結(jié)果追加時(shí)顯式復(fù)制append([]string{}, curr...)避免共享底層數(shù)組rust/0131-palindrome-partitioning.rsis_palindrome將String轉(zhuǎn)為as_bytes()后按字節(jié)比較swift/0131-palindrome-partitioning.swift先把s映射為[Character]數(shù)組再用Array(characters[start...end])切片判回文。以 C 為例倉(cāng)庫(kù)實(shí)現(xiàn)通過(guò)curr.pop_back()完成回溯撤銷(xiāo)與 Python 的part.pop()一一對(duì)應(yīng)class Solution { public: vectorvectorstring partition(string s) { vectorstring curr; vectorvectorstring result; dfs(s, 0, curr, result); return result; } private: void dfs(string s, int start, vectorstring curr, vectorvectorstring result) { if (start s.size()) { result.push_back(curr); return; } for (int i start; i s.size(); i) { if (isPalindrome(s, start, i)) { string str s.substr(start, i - start 1); curr.push_back(str); dfs(s, i 1, curr, result); curr.pop_back(); } } } bool isPalindrome(string s, int left, int right) { while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; } };5. DP 預(yù)計(jì)算回文表把回文校驗(yàn)降為 O(1)純回溯的問(wèn)題在于同一子串s[i..j]可能被不同遞歸分支反復(fù)校驗(yàn)最壞情況下每個(gè)子串被檢查O(2^n)次浪費(fèi)大量時(shí)間這也是 articles/palindrome-partitioning.md 末尾「Common Pitfalls」專(zhuān)門(mén)警示的點(diǎn)。優(yōu)化方案是用動(dòng)態(tài)規(guī)劃一次性預(yù)計(jì)算所有回文子串建立二維表dp[i][j]dp[i][j] true表示s[i..j]是回文按子串長(zhǎng)度l從 1 到n遞增填充長(zhǎng)度為 1 的單字符天然是回文更長(zhǎng)的子串滿足s[i] s[j]且內(nèi)部s[i1..j-1]是回文或長(zhǎng)度 ≤ 2。預(yù)計(jì)算完成后回溯中的isPali(s, i, j)調(diào)用全部替換為dp[i][j]的查表操作每次判定降為O(1)。時(shí)間復(fù)雜度仍為O(n * 2^n)答案數(shù)量主導(dǎo)但常數(shù)大幅下降額外空間變?yōu)镺(n^2)用于存放 DP 表。倉(cāng)庫(kù)中 java/0131-palindrome-partitioning.java 與 cpp/0131-palindrome-partitioning.cpp 均為純回溯版本而 articles/palindrome-partitioning.md 的第 3 節(jié)給出了完整的「Backtracking (DP)」多語(yǔ)言模板可直接作為該優(yōu)化的參考實(shí)現(xiàn)。6. 純遞歸返回式無(wú)全局狀態(tài)的聲明式寫(xiě)法另一種優(yōu)雅的實(shí)現(xiàn)是返回式遞歸articles/palindrome-partitioning.md 第 4 節(jié)「Recursion」不維護(hù)全局res與part而是讓dfs(i)返回從i出發(fā)的所有回文分割方案?；A(chǔ)條件i len(s)時(shí)返回[[]]一個(gè)空分割遞歸邏輯對(duì)每個(gè)滿足dp[i][j]的j先遞歸取得dfs(j1)的所有方案再把s[i..j]前置拼接到每個(gè)方案頭部組合公式即所有從 i 出發(fā)的分割 選擇回文 s[i..j] 所有從 j1 出發(fā)的分割。這種寫(xiě)法的優(yōu)點(diǎn)是完全無(wú)副作用、邏輯自明缺點(diǎn)是每個(gè)節(jié)點(diǎn)都要新建列表內(nèi)存分配更多。倉(cāng)庫(kù)的 java/0131-palindrome-partitioning.java 采用了與之思想一致的遞歸結(jié)構(gòu)對(duì)每個(gè)滿足回文條件的前綴s.substring(0, i1)遞歸求解后綴partition(s.substring(i1))并把前綴插到每個(gè)結(jié)果的頭部。7. 常見(jiàn)陷阱自查清單綜合提示文檔與 articles/palindrome-partitioning.md 的「Common Pitfalls」一節(jié)提交前務(wù)必檢查三點(diǎn)結(jié)果必須存拷貝而非引用part在回溯過(guò)程中會(huì)被反復(fù)修改直接res.append(part)會(huì)讓所有結(jié)果指向同一份最終被清空的列表。正確寫(xiě)法是part.copy()Python、new ArrayList(part)Java、append([]string{}, part...)Go等?；A(chǔ)條件用i len(s)或而非i len(s)i越過(guò)末尾意味著起點(diǎn)已經(jīng)消費(fèi)完整個(gè)字符串寫(xiě)成會(huì)漏掉恰好在末尾完成切分的合法方案或引發(fā)越界。避免無(wú)記憶化的重復(fù)回文校驗(yàn)同一子串在不同分支被反復(fù)判定會(huì)拖慢長(zhǎng)字符串場(chǎng)景建議用第 5 節(jié)的 DP 表緩存。8. 總結(jié)解法譜系與復(fù)雜度一覽解法狀態(tài)設(shè)計(jì)回文判定時(shí)間額外空間雙索引回溯Hint 2/3dfs(j, i)j 起點(diǎn) / i 終點(diǎn)每次雙指針 O(n)O(n·2^n)O(n)按起點(diǎn)枚舉回溯倉(cāng)庫(kù)主流實(shí)現(xiàn)dfs(i)枚舉終點(diǎn) j每次雙指針 O(n)O(n·2^n)O(n)回溯 DP 預(yù)計(jì)算dfs(i)dp[i][j]表查表 O(1)O(n·2^n)O(n^2)純遞歸返回式dfs(i)返回方案列表查表 O(1)O(n·2^n)O(n^2)四種寫(xiě)法共享同一復(fù)雜度上界O(n * 2^n)差異集中在常數(shù)因子與代碼風(fēng)格。練習(xí)時(shí)建議從按起點(diǎn)枚舉的回溯入手對(duì)應(yīng) python/0131-palindrome-partitioning.py再對(duì)照 articles/palindrome-partitioning.md 掌握雙索引、DP 預(yù)計(jì)算與返回式遞歸的變體最后用第 7 節(jié)的自查清單規(guī)避全部經(jīng)典陷阱——這套能力可以平移到「分割回文串 II」「單詞拆分」等同族回溯問(wèn)題。【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode 131 回文分割（Palindrome Partitioning）：回溯 + 雙索引遞歸與 O(n·2^n) 復(fù)雜度全解
LeetCode 131 回文分割Palindrome Partitioning回溯 雙索引遞歸與 O(n·2^n) 復(fù)雜度全解【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南以 hints/palindrome-partitioning.md 給出的解題提示為核心骨架系統(tǒng)講解 LeetCode 131「分割回文串」的完整解法從「為什么存在 2^n 種切分」的復(fù)雜度直覺(jué)出發(fā)逐步推導(dǎo)出雙索引回溯j 為當(dāng)前子串起點(diǎn)、i 為擴(kuò)展終點(diǎn)、按起點(diǎn)枚舉的回溯、DP 預(yù)計(jì)算回文表與純遞歸返回式四種實(shí)現(xiàn)并結(jié)合本倉(cāng)庫(kù)多語(yǔ)言源碼逐一印證。讀完你將掌握回文分割問(wèn)題的標(biāo)準(zhǔn)思考路徑、可直接運(yùn)行的代碼模板以及一份能寫(xiě)進(jìn)面試的復(fù)雜度分析。1. 問(wèn)題定義與目標(biāo)復(fù)雜度題目要求給定字符串s將s分割成若干子串使得每一個(gè)子串都是回文串返回所有可能的分割方案。例如s aab的輸出為[[a,a,b], [aa,b]]s a的輸出為[[a]]。提示文檔在開(kāi)篇即給出了本問(wèn)題的推薦復(fù)雜度目標(biāo)目標(biāo)解法應(yīng)達(dá)到O(n * 2^n)時(shí)間、O(n)空間其中n為輸入字符串長(zhǎng)度。這一目標(biāo)直接決定了算法形態(tài)由于答案數(shù)量本身是指數(shù)級(jí)的見(jiàn)下一節(jié)任何解法的下界都跑不出O(2^n)量級(jí)因此回溯Backtracking 剪枝就是最匹配的范式——它天然適合枚舉所有組合又通過(guò)「只接納回文子串」完成剪枝。倉(cāng)庫(kù)中的 cpp/0131-palindrome-partitioning.cpp 頭注釋也明確標(biāo)注了Time: O(n x 2^n)、Space: O(n)與提示文檔完全一致。2. 為什么有 2^n 種切分Hint 1 的復(fù)雜度直覺(jué)提示文檔的 Hint 1 給出了一個(gè)關(guān)鍵觀察對(duì)給定字符串存在2^n 種可能的切分因?yàn)樵诿總€(gè)索引處都有兩個(gè)決策要么在此處切分并開(kāi)始一個(gè)新的子串要么不切分繼續(xù)延伸當(dāng)前子串。理解這個(gè)結(jié)論是理解算法結(jié)構(gòu)的鑰匙。想象在字符串的n-1個(gè)相鄰字符之間放置「切/不切」的決策點(diǎn)切 → 當(dāng)前子串結(jié)束從下一位置開(kāi)啟新子串不切 → 當(dāng)前子串繼續(xù)向右延伸。每個(gè)位置兩個(gè)選擇組合起來(lái)恰好構(gòu)成一棵2^n 規(guī)模的決策樹(shù)?；厮菟惴ū举|(zhì)上就是遞歸遍歷這棵決策樹(shù)樹(shù)的高度為n字符串被逐字符消費(fèi)每一條從根到葉的路徑對(duì)應(yīng)一種切分方式其中「每個(gè)子串都是回文」的路徑才被采納進(jìn)結(jié)果。因此答案集最壞情況下有O(2^n)個(gè)方案每個(gè)方案平均長(zhǎng)度O(n)加上對(duì)每個(gè)方案做回文校驗(yàn)的開(kāi)銷(xiāo)總時(shí)間復(fù)雜度定格在O(n * 2^n)——這正是推薦復(fù)雜度目標(biāo)的時(shí)間來(lái)源。3. 雙索引回溯j, i對(duì)應(yīng) Hint 2 與 Hint 3 的核心實(shí)現(xiàn)3.1 指針含義與狀態(tài)設(shè)計(jì)提示文檔的 Hint 2 定義了本題最精煉的雙指針狀態(tài)j當(dāng)前待構(gòu)造子串的起始索引i當(dāng)前正在迭代擴(kuò)展的索引即子串的候選終點(diǎn)。每一步迭代中只有兩類(lèi)決策暫不切分保持j不變把i向右推進(jìn)一位dfs(j, i1)嘗試更長(zhǎng)的子串切分當(dāng)s[j..i]是回文時(shí)把該子串放入臨時(shí)列表part隨后令j i 1開(kāi)啟新的子串并從新起點(diǎn)繼續(xù)遞歸dfs(i1, i1)。遞歸的終止條件Hint 2 強(qiáng)調(diào)當(dāng)j走到字符串末尾時(shí)停止——這表示從起點(diǎn)到末尾的每一段都已被成功切分成回文當(dāng)前part即為一個(gè)合法答案。3.2 代碼模板PythonHint 3 補(bǔ)充了初始化細(xì)節(jié)從j 0, i 0和一個(gè)空的臨時(shí)列表part出發(fā)到達(dá)基礎(chǔ)條件時(shí)把part的拷貝加入結(jié)果集。據(jù)此得到的實(shí)現(xiàn)如下class Solution: def partition(self, s: str) - List[List[str]]: res, part [], [] def dfs(j, i): if i len(s): if i j: # 恰好完整切分完整個(gè)字符串 res.append(part.copy()) return if self.isPali(s, j, i): # 決策 2s[j..i] 是回文 → 切分 part.append(s[j : i 1]) dfs(i 1, i 1) # 新子串從 i1 開(kāi)始 part.pop() # 回溯撤銷(xiāo)選擇 dfs(j, i 1) # 決策 1不切分繼續(xù)延伸 dfs(0, 0) return res def isPali(self, s, l, r): while l r: if s[l] ! s[r]: return False l, r l 1, r - 1 return True注意兩個(gè)容易被忽略的細(xì)節(jié)基礎(chǔ)條件的雙重判斷i len(s)時(shí)只有i j才意味著「當(dāng)前子串恰好延伸到末尾且被完整消費(fèi)」此時(shí)part才是合法答案若i j說(shuō)明最后一串尚未確定是否為回文直接返回不收集?；匚呐卸╥sPali用雙指針向中間收縮l與r一旦出現(xiàn)字符不等立即返回False最壞O(n)這是 Hint 2 中明確要求的校驗(yàn)方式。3.3 該寫(xiě)法的復(fù)雜度時(shí)間O(n * 2^n)—— 枚舉全部切分組合每層做O(n)的回文校驗(yàn)空間O(n)額外空間遞歸棧深度 part列表不包含答案輸出本身占用的O(n * 2^n)。與 articles/palindrome-partitioning.md 中「Backtracking - I」一節(jié)的結(jié)論完全一致。4. 按起點(diǎn)枚舉的回溯倉(cāng)庫(kù)源碼的權(quán)威實(shí)現(xiàn)除雙索引寫(xiě)法外更常見(jiàn)、也更貼近本倉(cāng)庫(kù)實(shí)際提交的是按起點(diǎn)枚舉的回溯定義dfs(i)i是下一個(gè)子串的起點(diǎn)在i..n-1范圍內(nèi)枚舉終點(diǎn)j只要s[i..j]是回文就選取它并遞歸處理j1之后的剩余部分返回后pop撤銷(xiāo)?；A(chǔ)條件是i len(s)時(shí)把part的拷貝收入結(jié)果。倉(cāng)庫(kù)中的 python/0131-palindrome-partitioning.py 正是這一形態(tài)的完整實(shí)現(xiàn)class Solution: def partition(self, s: str) - List[List[str]]: res, part [], [] def dfs(i): if i len(s): res.append(part.copy()) return for j in range(i, len(s)): if self.isPali(s, i, j): part.append(s[i : j 1]) dfs(j 1) part.pop() dfs(0) return res def isPali(self, s, l, r): while l r: if s[l] ! s[r]: return False l, r l 1, r - 1 return True該解法與雙索引寫(xiě)法在決策語(yǔ)義上等價(jià)雙索引寫(xiě)法的「切分決策 不切分延伸」展開(kāi)后恰好覆蓋了按起點(diǎn)枚舉中「以i為起點(diǎn)、終點(diǎn)j從i掃到n-1」的全部子串區(qū)別僅在于狀態(tài)組織方式。按起點(diǎn)枚舉版更簡(jiǎn)潔是面試中最推薦的表達(dá)。同目錄下的多語(yǔ)言實(shí)現(xiàn)結(jié)構(gòu)一致可對(duì)照閱讀cpp/0131-palindrome-partitioning.cppdfs(s, start, curr, result)以start s.size()為終止條件isPalindrome雙指針校驗(yàn)go/0131-palindrome-partitioning.go用閉包backtrack(idx)結(jié)果追加時(shí)顯式復(fù)制append([]string{}, curr...)避免共享底層數(shù)組rust/0131-palindrome-partitioning.rsis_palindrome將String轉(zhuǎn)為as_bytes()后按字節(jié)比較swift/0131-palindrome-partitioning.swift先把s映射為[Character]數(shù)組再用Array(characters[start...end])切片判回文。以 C 為例倉(cāng)庫(kù)實(shí)現(xiàn)通過(guò)curr.pop_back()完成回溯撤銷(xiāo)與 Python 的part.pop()一一對(duì)應(yīng)class Solution { public: vectorvectorstring partition(string s) { vectorstring curr; vectorvectorstring result; dfs(s, 0, curr, result); return result; } private: void dfs(string s, int start, vectorstring curr, vectorvectorstring result) { if (start s.size()) { result.push_back(curr); return; } for (int i start; i s.size(); i) { if (isPalindrome(s, start, i)) { string str s.substr(start, i - start 1); curr.push_back(str); dfs(s, i 1, curr, result); curr.pop_back(); } } } bool isPalindrome(string s, int left, int right) { while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; } };5. DP 預(yù)計(jì)算回文表把回文校驗(yàn)降為 O(1)純回溯的問(wèn)題在于同一子串s[i..j]可能被不同遞歸分支反復(fù)校驗(yàn)最壞情況下每個(gè)子串被檢查O(2^n)次浪費(fèi)大量時(shí)間這也是 articles/palindrome-partitioning.md 末尾「Common Pitfalls」專(zhuān)門(mén)警示的點(diǎn)。優(yōu)化方案是用動(dòng)態(tài)規(guī)劃一次性預(yù)計(jì)算所有回文子串建立二維表dp[i][j]dp[i][j] true表示s[i..j]是回文按子串長(zhǎng)度l從 1 到n遞增填充長(zhǎng)度為 1 的單字符天然是回文更長(zhǎng)的子串滿足s[i] s[j]且內(nèi)部s[i1..j-1]是回文或長(zhǎng)度 ≤ 2。預(yù)計(jì)算完成后回溯中的isPali(s, i, j)調(diào)用全部替換為dp[i][j]的查表操作每次判定降為O(1)。時(shí)間復(fù)雜度仍為O(n * 2^n)答案數(shù)量主導(dǎo)但常數(shù)大幅下降額外空間變?yōu)镺(n^2)用于存放 DP 表。倉(cāng)庫(kù)中 java/0131-palindrome-partitioning.java 與 cpp/0131-palindrome-partitioning.cpp 均為純回溯版本而 articles/palindrome-partitioning.md 的第 3 節(jié)給出了完整的「Backtracking (DP)」多語(yǔ)言模板可直接作為該優(yōu)化的參考實(shí)現(xiàn)。6. 純遞歸返回式無(wú)全局狀態(tài)的聲明式寫(xiě)法另一種優(yōu)雅的實(shí)現(xiàn)是返回式遞歸articles/palindrome-partitioning.md 第 4 節(jié)「Recursion」不維護(hù)全局res與part而是讓dfs(i)返回從i出發(fā)的所有回文分割方案?；A(chǔ)條件i len(s)時(shí)返回[[]]一個(gè)空分割遞歸邏輯對(duì)每個(gè)滿足dp[i][j]的j先遞歸取得dfs(j1)的所有方案再把s[i..j]前置拼接到每個(gè)方案頭部組合公式即所有從 i 出發(fā)的分割 選擇回文 s[i..j] 所有從 j1 出發(fā)的分割。這種寫(xiě)法的優(yōu)點(diǎn)是完全無(wú)副作用、邏輯自明缺點(diǎn)是每個(gè)節(jié)點(diǎn)都要新建列表內(nèi)存分配更多。倉(cāng)庫(kù)的 java/0131-palindrome-partitioning.java 采用了與之思想一致的遞歸結(jié)構(gòu)對(duì)每個(gè)滿足回文條件的前綴s.substring(0, i1)遞歸求解后綴partition(s.substring(i1))并把前綴插到每個(gè)結(jié)果的頭部。7. 常見(jiàn)陷阱自查清單綜合提示文檔與 articles/palindrome-partitioning.md 的「Common Pitfalls」一節(jié)提交前務(wù)必檢查三點(diǎn)結(jié)果必須存拷貝而非引用part在回溯過(guò)程中會(huì)被反復(fù)修改直接res.append(part)會(huì)讓所有結(jié)果指向同一份最終被清空的列表。正確寫(xiě)法是part.copy()Python、new ArrayList(part)Java、append([]string{}, part...)Go等?；A(chǔ)條件用i len(s)或而非i len(s)i越過(guò)末尾意味著起點(diǎn)已經(jīng)消費(fèi)完整個(gè)字符串寫(xiě)成會(huì)漏掉恰好在末尾完成切分的合法方案或引發(fā)越界。避免無(wú)記憶化的重復(fù)回文校驗(yàn)同一子串在不同分支被反復(fù)判定會(huì)拖慢長(zhǎng)字符串場(chǎng)景建議用第 5 節(jié)的 DP 表緩存。8. 總結(jié)解法譜系與復(fù)雜度一覽解法狀態(tài)設(shè)計(jì)回文判定時(shí)間額外空間雙索引回溯Hint 2/3dfs(j, i)j 起點(diǎn) / i 終點(diǎn)每次雙指針 O(n)O(n·2^n)O(n)按起點(diǎn)枚舉回溯倉(cāng)庫(kù)主流實(shí)現(xiàn)dfs(i)枚舉終點(diǎn) j每次雙指針 O(n)O(n·2^n)O(n)回溯 DP 預(yù)計(jì)算dfs(i)dp[i][j]表查表 O(1)O(n·2^n)O(n^2)純遞歸返回式dfs(i)返回方案列表查表 O(1)O(n·2^n)O(n^2)四種寫(xiě)法共享同一復(fù)雜度上界O(n * 2^n)差異集中在常數(shù)因子與代碼風(fēng)格。練習(xí)時(shí)建議從按起點(diǎn)枚舉的回溯入手對(duì)應(yīng) python/0131-palindrome-partitioning.py再對(duì)照 articles/palindrome-partitioning.md 掌握雙索引、DP 預(yù)計(jì)算與返回式遞歸的變體最后用第 7 節(jié)的自查清單規(guī)避全部經(jīng)典陷阱——這套能力可以平移到「分割回文串 II」「單詞拆分」等同族回溯問(wèn)題。【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考