回文字符串与动态规划

LeetCode2472. 不重叠回文子字符串的最大数目

题目描述
给你一个字符串 $s$ 和一个正整数 $k$ 。
从字符串 $s$ 中选出一组满足下述条件且不重叠的子字符串：

• 每个子字符串的长度至少为 $k$。
• 每个子字符串是一个回文串。

返回最优方案中能选择的子字符串的最大数目。
子字符串是字符串中一个连续的字符序列。
$1<=k<=s.length<=2000$
$s$ 仅由小写字母组成

示例 1
输入：s = “abaccdbbd”, k = 3
输出：2
解释：选 aba 和 dbbd

思路
动态规划
状态定义：$dp[i]$表示字符串$s[0,i-1]$中最大子字符串的数目。
初始状态：$dp[0]=0$
状态转移：
(1) $dp[i+1]=dp[i]$，$s[i]$不参与构成满足条件的回文子字符串；
(2) $dp[r+1]=max(dp[r],dp[l]+1)$，$s[l,r]$是满足条件的回文串。

在使用中心扩展法搜索回文子字符串时，找到长度大于等于k即可停止搜索，根据贪心的思想，此时统计的数目才会最大。

代码

public int maxPalindromes(String s, int k) {
    int n = s.length();
    int[] dp = new int[n + 1];
    for (int t = 0; t < 2 * n - 1; t++) {
        int i = t / 2, j = t / 2 + t % 2;
        dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
            if (j - i + 1 >= k) {
                dp[j + 1] = Math.max(dp[j], dp[i] + 1);
                break;
            }
            i--;j++;
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode132. 分割回文串Ⅱ

题目描述
给你一个字符串 $s$，请你将 $s$ 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数。
$1<=s.length<=2000$
$s$ 仅由小写字母组成

示例 1
输入：s = “aab”
输出：1
解释：分割一次分成 [“aa”, “b”]

思路
动态规划
状态定义：$dp[i]$表示字符串$s[0,i-1]$的最少分割次数。
初始状态：$dp[0]=-1$，因为如果 $s$ 本身是回文字符串不需要分割。
状态转移：$dp[r+1]=min(dp[r+1],dp[r]+1,dp[l]+1)$，$s[l,r]$是满足条件的回文串。

代码

public int minCut(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    Arrays.fill(dp, 5000);
    dp[0] = -1;
    for (int k = 0; k < 2 * n - 1; k++) {
        int i = k / 2, j = k / 2 + k % 2;
        for (; i >= 0 && j < n && s.charAt(i) == s.charAt(j); i--,j++) {
            dp[j + 1] = Math.min(dp[j + 1], Math.min(dp[j] + 1, dp[i] + 1));
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

当然本题还有其他动态规划方法。

这两题在搜索回文字符串时都使用了中心扩展法。
一个长度为 $n$ 的字符串，回文串的中心位置共 $2n-1$ 种可能，分别为 $(0,0),(0,1),(1,1),(1,2),...(k/2,k/2+k\%2),...(n-2,n-2),(n-2,n-1),(n-1,n-1)$