标签：子串 start 算法 result 应用 回溯 path dp 回文

目录

• 应用
  • 应用1：Leetcode 131. 分割回文串
    • 题目
    • 分析
    • 代码实现

应用

应用1：Leetcode 131. 分割回文串

题目

131. 分割回文串

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

分析

首先使用动态规划，计算所有的子串是否是回文子串，然后再通过回溯的方式枚举所有的子串组合即可。

这里，我们用 \(f(i,j)\) 表示子串 \(s[i \cdots j]\) 是否是回文子串。

容易看出来，如果 \(s[i \cdots j]\) 满足以下条件之一：

• 子串长度为 \(1\)，此时，\(i = j\);

• 子串为空串，此时，\(i \gt j\)；

• 子串的首尾字符相同，即\(s[i] = s[j]\)，且 \(s[i + 1\cdots j - 1]\) 是回文子串，此时，它可以由上一个状态 \(f(i + 1, j - 1)\) 转移而来。

那么，\(s[i \cdots j]\) 就是回文子串。

因此，它的状态转移方程为：

\[f(i,j) = \begin{cases} True,&i \ge j\\ (s[i] == s[j]) \land f(i + 1, j - 1), &otherwise \end{cases} \]

其中，\(\land\) 表示逻辑与运算。

然后，我们再使用回溯的方式，枚举所有的子串，通过 \(f(i,j)\) 判断子串是否是回文子串。

代码实现

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]

        result = list()
        self.dfs(dp, s, n, list(), result, 0)
        return result

    def dfs(self, dp, s, n, path, result, start):
        """ 通过回溯的方式，枚举所有的子串组合 """
        if start == n:
            result.append(path[:])

        for i in range(start, n):
            if dp[start][i]:
                path.append(s[start:i + 1])
                self.dfs(dp, s, n, path, result, i + 1)
                path.pop()
        return

---

参考：

• 分割回文串

标签：子串,start,算法,result,应用,回溯,path,dp,回文
From： https://www.cnblogs.com/larry1024/p/17529373.html