leetcode132：分割回文串II

题目链接

leetcode

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
返回符合要求的 最少分割次数 。

C++ 代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
    动态规划，一共进行两次。

    第一次：计算出每个子串是否为回文串。
    状态表示：
        st[i][j] 表示 s[i...j] 是否是回文串
    转移方程：
        s[i...j] 是回文串，当且仅当 s[i] == s[j] 并且 s[i+1...j−1] 是回文串
    边界情况：
        若 s[i...j] 长度小于等于 2，则 st[i][j] = (s[i] == s[j])

    在第一次的基础上，进行第二次。
    状态表示：
        f[i] 表示把前 i 个字符划分成回文串，最少划分成几部分
    状态转移：
        枚举最后一段回文串的起点 j，根据 st[j][i] 可知 s[j...i] 是否为回文串。
        若是回文串，则 f[i] = f[j−1] + 1。
    边界情况：
        0 个字符可以划分成 0 部分，所以 f[0] = 0。
    题目求最少切几刀，所以答案是 f[n] − 1。

    时间复杂度：O(n^2)
    空间复杂度：O(n^2)
*/
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> st(n + 1, vector<bool>(n + 1));
        vector<int> f(n + 1, INT_MAX);

        for (int j = 1; j <= n; j ++) {
            for (int i = 1; i <= n; i ++) {
                if (i == j) st[i][j] = true;
                else if (s[i] == s[j]) {
                    if (i + 1 > j - 1 || st[i + 1][j - 1]) st[i][j] = true;
                }
            }
        }

        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i; j ++) {
                if (st[j][i])
                    f[i] = min(f[i], f[j - 1] + 1);
            }
        }

        return f[n] - 1;
    }
};

// 思路同上
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> st(n + 1, vector<bool>(n + 1, true));
        vector<int> f(n + 1, INT_MAX);

        for (int i = n; i >= 1; i --) {
            for (int j = i + 1; j <= n; j ++) {
                st[i][j] = (s[i] == s[j]) && st[i + 1][j - 1];
            }
        }

        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i; j ++) {
                if (st[j][i])
                    f[i] = min(f[i], f[j - 1] + 1);
            }
        }

        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i; j ++) {
                if (st[j][i])
                    f[i] = min(f[i], f[j - 1] + 1);
            }
        }

        return f[n] - 1;
    }
};
#leetcode
leetcode132：分割回文串II
https://lcf163.github.io/2024/04/07/leetcode132：分割回文串II/
作者
乘风的小站
发布于
2024年4月7日
许可协议