131-palindrome-partitioning.md

131. Palindrome Partitioning - 分割回文串

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

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

示例:

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

---

题目标签：Backtracking

题目链接：LeetCode / LeetCode中国

题解

本题可以使用递归。思路是：如果是空串，就返回[[]]；否则，分割s，如果分割处左侧是回文串，就把它和右侧的回文子串组合联合起来。

Language	Runtime	Memory
python3	228 ms	N/A

class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if not s:
            return [[]]
        res = []
        for i in range(len(s)):
            if s[:i+1] == s[:i+1][::-1]:
                for ss in self.partition(s[i+1:]):
                    res.append([s[:i+1], *ss])
        return res