131 Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

solution

• 切割问题其实是一种组合问题，但是要理解如何模拟切割。联想：切割一个点，和之前排列组合问题中的取一个树

• 注意：判断条件的时候，一种是判断整体是否满足条件，还有一种是判断每一步是否符合条件加入

• 为了不重复切割同一位置，start_index来做标记下一轮递归的起始位置(切割线)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        path = []
        res = []
        self.dfs(path, res, s, start=0)
        return res

    def dfs(self, path, res, s, start):
        if start >= len(s):
            res.append(path.copy())
            return
        
        for i in range(start, len(s)):  # 注意范围
            if self.is_valid(s, start=start, end=i):  # 左闭右闭
                path.append(s[start:(i+1)])  # 左闭右开
                self.dfs(path, res, s, i+1)
                path.pop()

    def is_valid(self, string, start, end):
        l = start
        r = end
        while r >= l:
            if string[r] == string[l]:
                r -= 1
                l += 1
            else:
                return False
        return True
        

时间复杂度：O(n⋅2^n) 空间复杂度：O(n⋅2^n)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        path = []
        res = []
        self.dfs(s, path, res, start=0)
        return res
    
    def dfs(self, s, path, res, start):
        if start >= len(s):
            res.append(path[:])
            return
        
        for i in range(start, len(s)):
            temp = s[start:i+1]
            if temp == temp[::-1]:
                path.append(temp)
                self.dfs(s, path, res, i+1)
                path.pop()
            else:
                continue

follow up

132. Palindrome Partitioning II

139 Word Break