目录

0131:分割回文串(★)

力扣第 131 题

题目

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

相似问题:

分析

按第一个回文子串的长度递归即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        @cache
        def dfs(s):
            if not s:
                return [[]]
            res = []
            for i in range(1,len(s)+1):
                if s[:i]==s[:i][::-1]:
                    res.extend([s[:i]]+sub for sub in dfs(s[i:]))
            return res
        return dfs(s)

92 ms