# 0131. 分割回文串 ## 題目地址(131. 分割回文串) <https://leetcode-cn.com/problems/palindrome-partitioning/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個字符串 s，將 s 分割成一些子串，使每個子串都是回文串。 返回 s 所有可能的分割方案。 示例: 輸入: "aab" 輸出: [ ["aa","b"], ["a","a","b"] ] ``` ``` ## 前置知識 - 回溯法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一道求解所有可能性的題目， 這時候可以考慮使用回溯法。 回溯法解題的模板我們已經在很多題目中用過了， 這里就不多說了。大家可以結合其他幾道題目加深一下理解。 這里我畫了一個圖：  > 圖是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，僅做參考。 ## 關鍵點解析 - 回溯法 ## 代碼 - 語言支持：JS，Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=131 lang=javascript * * [131] Palindrome Partitioning */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">isPalindrom</span>(<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">let</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> right = s.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>(left < right && s[left] === s[right]) { left++; right--; } <span class="hljs-keyword">return</span> left >= right; } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">backtrack</span>(<span class="hljs-params">s, list, tempList, start</span>) </span>{ <span class="hljs-keyword">const</span> sliced = s.slice(start); <span class="hljs-keyword">if</span> (isPalindrom(sliced) && (tempList.join(<span class="hljs-string">""</span>).length === s.length)) list.push([...tempList]); <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < sliced.length; i++) { <span class="hljs-keyword">const</span> sub = sliced.slice(<span class="hljs-params">0</span>, i + <span class="hljs-params">1</span>); <span class="hljs-keyword">if</span> (isPalindrom(sub)) { tempList.push(sub); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">continue</span>; } backtrack(s, list, tempList, start + i + <span class="hljs-params">1</span>); tempList.pop(); } } <span class="hljs-title">/** * @param {string} s * @return {string[][]} */</span> <span class="hljs-keyword">var</span> partition = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s</span>) </span>{ <span class="hljs-title">// "aab"</span> <span class="hljs-title">// ["aa", "b"]</span> <span class="hljs-title">// ["a", "a", "b"]</span> <span class="hljs-keyword">const</span> list = []; backtrack(s, list, [], <span class="hljs-params">0</span>); <span class="hljs-keyword">return</span> list; }; ``` ``` ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(self, s: str)</span> -> List[List[str]]:</span> <span class="hljs-string">"""回溯法"""</span> res = [] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(s, tmp)</span>:</span> <span class="hljs-string">""" 如果是空字符串，說明已經處理完畢 否則逐個字符往前測試，判斷是否是回文 如果是，則處理剩余字符串，并將已經得到的列表作為參數 """</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s: res.append(tmp) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, len(s) + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> s[:i] == s[:i][::<span class="hljs-params">-1</span>]: helper(s[i:], tmp + [s[:i]]) helper(s, []) <span class="hljs-keyword">return</span> res ``` ``` ## 相關題目 - [39.combination-sum](39.combination-sum.html) - [40.combination-sum-ii](40.combination-sum-ii.html) - [46.permutations](46.permutations.html) - [47.permutations-ii](47.permutations-ii.html) - [78.subsets](78.subsets.html) - [90.subsets-ii](90.subsets-ii.html) - [113.path-sum-ii](113.path-sum-ii.html)