字符串分割成回文串：回溯算法和动态规划实现

字符串分割成回文串：回溯算法和动态规划实现

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

思路：

1. 回溯算法，枚举所有可能的分割方案
2. 判断子串是否为回文串可以使用动态规划或双指针两种方法

动态规划：

1. 定义状态：dp[i][j] 表示 s[i...j] 是否为回文串
2. 状态转移方程：dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
3. 边界条件：dp[i][i] = true, dp[i][i+1] = s[i] == s[i+1]

双指针：

1. 从两端向中间遍历，判断左右两个字符是否相等
2. 如果相等，继续向中间移动指针；如果不相等，说明不是回文串

代码：（使用动态规划）

def partition(s: str) -> List[List[str]]:
    n = len(s)
    dp = [[False for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i] = True
    for i in range(n - 1):
        dp[i][i + 1] = s[i] == s[i + 1]
    for i in range(n - 2, -1, -1):
        for j in range(i + 2, n):
            dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]

    def backtrack(index: int, path: List[str]):
        if index == n:
            result.append(path.copy())
            return
        for j in range(index, n):
            if dp[index][j]:
                path.append(s[index:j + 1])
                backtrack(j + 1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result