# 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)