LeetCode132-分割回文串II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/palindrome-partitioning-ii/

中文链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii/

题目详述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

1
2
3
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

题目详解

动态规划。

  • 类似于 LeetCode5-最长回文子串，可以采用从中心向两边扩展，分为奇数长度和偶数长度两种情况。
  • 定义 f[i] 表示将 s[0, i] 分割成回文串的最少分割次数，容易知道最差情况每个字符当作一个回文串，则 f[i] = i。
  • 从小到大枚举回文串的中心，从中心向两边扩展，在这个过程中进行状态转移。
  • 如果 s[i, j] 为回文串，则 f[j] 可以由 f[i - 1] 转移得到。 f[j] = min(f[j], f[i - 1] + 1)，需满足 i > 0；若 i == 0，说明不需要分割，f[j] = 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00132 {

    public int minCut(String s) {
        int n = s.length();
        // f[i] 表示将 s[0, i] 分割成回文串的最少分割次数
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
        for (int i = 0; i < n; ++i) {
            expand(s, i, i, f);
            expand(s, i, i + 1, f);
        }
        return f[n - 1];
    }

    private void expand(String s, int i, int j, int[] f) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            f[j] = Math.min(f[j], i > 0 ? f[i - 1] + 1 : 0);
            --i;
            ++j;
        }
    }
}
  • 另一种动态规划的方法，一共进行两次动态规划。
  • 第一次动规：计算出每个字串是否是回文串。
    • 状态 c[i][j] 表示 s[i, j] 是否为回文串。
    • 转移方程： s[i, j] 为回文串当且仅当 s[i] == s[j] 并且 s[i + 1, j - 1] 为回文串。
    • 边界情况：如果 s[i, j] 的长度小于等于2，则 c[i][j] = s[i] == s[j]。
  • 第二次动归，同上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LeetCode_00132 {

    public int minCut(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        // c[i][j] 表示 cs[i, j] 是否为回文串
        boolean[][] c = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                c[j][i] = cs[j] == cs[i] && (j + 1 > i - 1 || c[j + 1][i - 1]);
            }
        }
        // f[i] 表示将 s[0, i] 分割成回文串的最少分割次数
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (c[j][i]) {
                    f[i] = Math.min(f[i], j > 0 ? f[j - 1] + 1 : 0);
                }
            }
        }
        return f[n - 1];
    }
}