[LeetCode]131 分割回文段

题目描述

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

示例

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

思路

  • 一次遍历，检查首尾是否相同
  • 若相同，进入递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        self.res = []
        self.temp = []
        def sub_partition(string):
            if string == string[::-1]:
                self.temp.append(string)
                self.res.append(copy.copy(self.temp))
                self.temp.pop()
            for i in range(1,len(string)):
                a = string[:i]
                if a == a[::-1]:
                    self.temp.append(a)
                    sub_partition(string[i:])
                    self.temp.pop()
        sub_partition(s)
        return self.res