↓Skip to main content
  1. Posts/

LeetCode-131 分割回文串

·1 min·
Table of Contents

LeetCode-131 分割回文串 #

Solution 1 #

预处理区间是否是回文串, 回溯.

代码如下:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]
        for l in range(1, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                dp[i][j] = (dp[i + 1][j - 1] if i + 1 <= j - 1 else True) and s[i] == s[j]

        ans = []
        def f(i, path):
            if i == n:
                ans.append(path.copy())
                return
            for j in range(i, n):
                if dp[i][j]:
                    path.append(s[i:j + 1])
                    f(j + 1, path)
                    path.pop()
            return
        f(0, [])
        return ans