python实现leetcode之131. 分割回文串

解题思路

随便找一个点，如果前半部分是回文，他就是分割的第一个单词
将这个单词附加在后面的每一种分割前面，就是完整的分割方案

131. 分割回文串

代码

class Solution:
    def partition(self, s):
        if not s: return [[]]
        rtv = []
        for i in range(1, len(s)+1):
            if is_palindrome(s[:i]):
                first = s[:i]
                rest = self.partition(s[i:])
                for r in rest:
                    rtv.append([first, *r])
        return rtv


def is_palindrome(s):
    if not s: return False
    low, high = 0, len(s)-1
    while low < high:
        if s[low] != s[high]:
            return False
        low += 1
        high -= 1
    return True