分割回文串
- 难度: 中等
- 通过率: 38.7%
- 题目链接:https://leetcode-cn.com/problems/palindrome-partitioning
题目描述
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
解法:
直接采用回溯法暴力搜索即可。
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
def helper(s, res):
if not s:
result.append(res)
return
for i in range(len(s)):
if s[:i+1] == s[:i+1][::-1]:
helper(s[i+1:], res + [s[:i+1]])
helper(s, [])
return result