题目
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a"
输出:[["a"]]
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
思路:
dfs
往后遍历每个位置
代码
class Solution:
def partition(self, s: str) -> List[List[str]]:
res, path, n = [], [], len(s)
def dfs(i):
if i == n:
res.append(path.copy())
return
for j in range(i, n):
t = s[i: j + 1]
if t == t[::-1]:
path.append(t)
dfs(j + 1)
path.pop()
dfs(0)
return res
标签:分割,示例,res,dfs,131,path,LeetCode,回文
From: https://www.cnblogs.com/basilicata/p/17927939.html