Leetcode 131 Palindrome Partitioning

发表于 |

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

示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

分析：

  1. 这种题其实都是有固定解法的，显然partition(s)定义为s所能组成的回文字符串列表
  2. 那么我们依次截取s的前i个字符，判断其是否为回文字符串。若是，则显然 s[:i] + l for l in partition(s[i:])，就为最后的答案
  3. 例如aab,先判断第一个’a’为回文,则剩余的partition(‘ab’)会返回[[‘a’,’b’]]，然后用第一个’a’分别加上返回的值变为[[‘a’,’a’,’b’]]
  4. 然后判断前两个’aa’为回文，剩余的partition(‘b’)会返回[[‘b’]],加上变为[[‘aa’,’b’]]

思路：

  1. 定义函数isPalin(s)判断s是否为回文字符串
  2. 设定递归终止条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        def isPalin(s):
	        return s == s[::-1]
        # 只要终止条件设定好，递推式一写答案自然就出来，还是有点神奇的
        if len(s) == 1: return [[s]]

        res = []
        for i in range(1,len(s)):
            if isPalin(s[:i]):
                for l in self.partition(s[i:]):
                    res.append([s[:i]] + l)
        
        # 上面的递归过程没有将s本身考虑进去，因为i遍历到最后时s[i:]已经没有东西了，不存在l的话，res也就没有append操作了
        if isPalin(s): res.append([s])
        return res


22 / 22 test cases passed.
Difficulty: Medium
Runtime: 196 ms,beats 34.78%