[LeetCode]131. 分割回文串(Palindrome Partitioning)

题目描述

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

解题思路

回溯法。对于该字符串,递归每一个位置,将字符串分割为两部分,判断左边是否为回文,若是,则左边加上右边递归的结果即为一种问题的解。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def partition(self, s: str) -> List[List[str]]:
if len(s) == 0:
return [[]]
if len(s) == 1:
return [[s]]
res = []
for i in range(1, len(s) + 1):
left = s[:i]
right = s[i:]
if left != left[::-1]:
continue
right = self.partition(right)
for j in range(len(right)):
res.append([left] + right[j])
return res