class Solution {
public:
int minCut(string s) {
}
};
剑指 Offer II 094. 最少回文分割
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s 仅由小写英文字母组成
注意：本题与主站 132 题相同： https://leetcode.cn/problems/palindrome-partitioning-ii/
原站题解
java 解法, 执行用时: 30 ms, 内存消耗: 43.2 MB, 提交时间: 2023-01-12 09:51:06
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] g = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
}
}
int[] f = new int[n];
Arrays.fill(f, Integer.MAX_VALUE);
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
}
javascript 解法, 执行用时: 156 ms, 内存消耗: 93.1 MB, 提交时间: 2023-01-12 09:50:45
/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
const n = s.length;
const g = new Array(n).fill(0).map(() => new Array(n).fill(true));
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
g[i][j] = s[i] == s[j] && g[i + 1][j - 1];
}
}
const f = new Array(n).fill(Number.MAX_SAFE_INTEGER);
for (let i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (let j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
};
golang 解法, 执行用时: 16 ms, 内存消耗: 7.3 MB, 提交时间: 2023-01-12 09:50:27
func minCut(s string) int {
n := len(s)
g := make([][]bool, n)
for i := range g {
g[i] = make([]bool, n)
for j := range g[i] {
g[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
g[i][j] = s[i] == s[j] && g[i+1][j-1]
}
}
f := make([]int, n)
for i := range f {
if g[0][i] {
continue
}
f[i] = math.MaxInt64
for j := 0; j < i; j++ {
if g[j+1][i] && f[j]+1 < f[i] {
f[i] = f[j] + 1
}
}
}
return f[n-1]
}
python3 解法, 执行用时: 624 ms, 内存消耗: 42.8 MB, 提交时间: 2023-01-12 09:50:09
'''
设 f[i] 表示字符串的前缀 s[0..i] 的最少分割次数。要想得出 f[i] 的值，
我们可以考虑枚举 s[0..i] 分割出的最后一个回文串，这样我们就可以写出状态转移方程。
'''
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
g = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]
f = [float("inf")] * n
for i in range(n):
if g[0][i]:
f[i] = 0
else:
for j in range(i):
if g[j + 1][i]:
f[i] = min(f[i], f[j] + 1)
return f[n - 1]