分割回文串II

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

LeetCode每日一题，132. Palindrome Partitioning II

先看题目描述

6QeyQO.png

大意就是给定一个字符串 s，让我们将 s 分割成多个回文子串，并返回最小的分割次数

算法和思路

动态规划

  • 状态方程定义：f[i] 表示将子串 s[0：i] 分割为多个回文子串的最小分割次数
  • 状态转移方程：若 s[0：i] 为回文串，则 f[i] = 0；否则 f[i] = min{f[j]} + 1，其中 0 <= j < i 且 s[j + 1：i] 为回文串
  • 最后返回 f[len - 1] 即可

即我们枚举最后一个回文串的起始位置 j + 1，保证 s[j + 1：i] 是一个回文串，那么 f[i] 就可以从 f[j] 转移而来，附加一次额外的分割次数。若 s[0：i] 本身就是回文串的话，则不用分割，其最小分割次数为 0

至于如何快速的判断 s[j + 1：i] 是否为回文串，我们可以使用动态规划进行预处理

  • 状态方程定义：布尔数组 dp[i][j] 表示子串 s[i：j] 是否为回文串
  • 状态转移方程：dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]

将 dp 数组预先构建好后便可在 O(1) 的时间内判断子串 s[j + 1：i] 是否为回文串

ps：感觉这题中动态数组 f 的状态转移方程有点类似 LIS问题(最长上升序列问题)的状态转移方程，其状态转移方程为 f[i] = max{f[j]} + 1，其中 0 <= j < i 且 nums[j] < nums[i]

算法源码

动态规划

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
28
29
30
31
32
33
34
35
import java.util.Arrays;

class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] f = new int[len];
        char[] cs = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (j - i <= 2) {
                    dp[i][j] = cs[i] == cs[j];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
                }
            }
        }
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < len; i++) {
            if (dp[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; j++) {
                    if (dp[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }
        return f[len - 1];
    }
}

下面是使用 回溯搜索 + 动态规划 实现的代码，基本上和昨天的题思路是一致的，结果跑超时了

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
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    private int len;
    private int count = -1;
    private int ans = Integer.MAX_VALUE;
    private boolean[][] dp;

    public int minCut(String s) {
        len = s.length();
        char[] cs = s.toCharArray();
        dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (j - i <= 2) {
                    dp[i][j] = cs[i] == cs[j];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
                }
            }
        }
        dfs(s, 0);
        return ans;
    }

    private void dfs(String s, int index) {
        if (index == len) {
            ans = Math.min(ans, count);
            return;
        }
        for (int i = len - 1; i >= index; i--) {
            if (dp[index][i]) {
                count++;
                dfs(s, i + 1);
                count--;
            }
        }
    }
}