class Solution {
public:
int minCut(string s) {
}
};
132. 分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s 仅由小写英文字母组成相似题目
原站题解
golang 解法, 执行用时: 23 ms, 内存消耗: 12.2 MB, 提交时间: 2025-03-02 08:57:22
func minCut1(s string) int {
n := len(s)
palMemo := make([][]int8, n)
for i := range palMemo {
palMemo[i] = make([]int8, n)
for j := range palMemo[i] {
palMemo[i][j] = -1 // -1 表示没有计算过
}
}
// 判断 s[l:r+1] 是否是回文串
var isPalindrome func(int, int) bool
isPalindrome = func(l, r int) bool {
if l >= r {
return true
}
p := &palMemo[l][r]
if *p != -1 { // 之前计算过
return *p == 1
}
res := s[l] == s[r] && isPalindrome(l+1, r-1)
if res {
*p = 1 // 记忆化
} else {
*p = 0
}
return res
}
dfsMemo := make([]int, n)
for i := range dfsMemo {
dfsMemo[i] = -1 // -1 表示没有计算过
}
var dfs func(int) int
dfs = func(r int) int {
if isPalindrome(0, r) { // 已是回文串，无需分割
return 0
}
p := &dfsMemo[r]
if *p != -1 { // 之前计算过
return *p
}
res := math.MaxInt
for l := 1; l <= r; l++ { // 枚举分割位置
if isPalindrome(l, r) {
res = min(res, dfs(l-1)+1) // 在 l-1 和 l 之间切一刀
}
}
*p = res // 记忆化
return res
}
return dfs(n - 1)
}
// 递推
func minCut(s string) int {
n := len(s)
// isPalindrome[l][r] 表示 s[l:r+1] 是否为回文串
isPalindrome := make([][]bool, n)
for i := range isPalindrome {
isPalindrome[i] = make([]bool, n)
for j := range isPalindrome[i] {
isPalindrome[i][j] = true
}
}
for l := n - 2; l >= 0; l-- {
for r := l + 1; r < n; r++ {
isPalindrome[l][r] = s[l] == s[r] && isPalindrome[l+1][r-1]
}
}
f := make([]int, n)
for r, isPal := range isPalindrome[0] {
if isPal { // 已是回文串，无需分割
continue
}
res := math.MaxInt
for l := 1; l <= r; l++ { // 枚举分割位置
if isPalindrome[l][r] {
res = min(res, f[l-1]+1) // 在 l-1 和 l 之间切一刀
}
}
f[r] = res
}
return f[n-1]
}
cpp 解法, 执行用时: 67 ms, 内存消耗: 61.4 MB, 提交时间: 2025-03-02 08:56:42
class Solution {
public:
int minCut1(string s) {
int n = s.size();
vector pal_memo(n, vector<int>(n, -1)); // -1 表示没有计算过
auto is_palindrome = [&](this auto&& is_palindrome, int l, int r) -> bool {
if (l >= r) {
return true;
}
int& res = pal_memo[l][r]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
return res = s[l] == s[r] && is_palindrome(l + 1, r - 1);
};
vector<int> dfs_memo(n, INT_MAX); // INT_MAX 表示没有计算过
auto dfs = [&](this auto&& dfs, int r) -> int {
if (is_palindrome(0, r)) { // 已是回文串，无需分割
return 0;
}
int& res = dfs_memo[r]; // 注意这里是引用
if (res != INT_MAX) { // 之前计算过
return res;
}
for (int l = 1; l <= r; l++) { // 枚举分割位置
if (is_palindrome(l, r)) {
res = min(res, dfs(l - 1) + 1); // 在 l-1 和 l 之间切一刀
}
}
return res;
};
return dfs(n - 1);
}
// 递推
int minCut(string s) {
int n = s.size();
// is_palindrome[l][r] 表示 s[l] 到 s[r] 是否为回文串
vector is_palindrome(n, vector<int>(n, true));
for (int l = n - 2; l >= 0; l--) {
for (int r = l + 1; r < n; r++) {
is_palindrome[l][r] = s[l] == s[r] && is_palindrome[l + 1][r - 1];
}
}
vector<int> f(n);
for (int r = 0; r < n; r++) {
if (is_palindrome[0][r]) { // 已是回文串，无需分割
continue;
}
int res = INT_MAX;
for (int l = 1; l <= r; l++) { // 枚举分割位置
if (is_palindrome[l][r]) {
res = min(res, f[l - 1] + 1); // 在 l-1 和 l 之间切一刀
}
}
f[r] = res;
}
return f[n - 1];
}
};
python3 解法, 执行用时: 539 ms, 内存消耗: 48.2 MB, 提交时间: 2025-03-02 08:55:46
class Solution:
def minCut1(self, s: str) -> int:
# 返回 s[l:r+1] 是否为回文串
@cache # 缓存装饰器，避免重复计算 is_palindrome（一行代码实现记忆化）
def is_palindrome(l: int, r: int) -> bool:
if l >= r:
return True
return s[l] == s[r] and is_palindrome(l + 1, r - 1)
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(r: int) -> int:
if is_palindrome(0, r): # 已是回文串，无需分割
return 0
res = inf
for l in range(1, r + 1): # 枚举分割位置
if is_palindrome(l, r):
res = min(res, dfs(l - 1) + 1) # 在 l-1 和 l 之间切一刀
return res
return dfs(len(s) - 1)
# 递推
def minCut(self, s: str) -> int:
n = len(s)
# is_palindrome[l][r] 表示 s[l:r+1] 是否为回文串
is_palindrome = [[True] * n for _ in range(n)]
for l in range(n - 2, -1, -1):
for r in range(l + 1, n):
is_palindrome[l][r] = s[l] == s[r] and is_palindrome[l + 1][r - 1]
f = [0] * n
for r, is_pal in enumerate(is_palindrome[0]):
if is_pal: # 已是回文串，无需分割
continue
res = inf
for l in range(1, r + 1): # 枚举分割位置
if is_palindrome[l][r]:
res = min(res, f[l - 1] + 1) # 在 l-1 和 l 之间切一刀
f[r] = res
return f[-1]
golang 解法, 执行用时: 16 ms, 内存消耗: 7.3 MB, 提交时间: 2023-01-12 09:52:56
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 解法, 执行用时: 596 ms, 内存消耗: 42.7 MB, 提交时间: 2023-01-12 09:52:36
class Solution:
def minCut(self, s: str) -> int:
n=len(s)
dp=[[False]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
for j in range(i,n):
if s[i]==s[j]:
if j-i<=1:
dp[i][j]=True
else:
dp[i][j]=dp[i+1][j-1]
f=[0]*n
f[0]=1
for i in range(1,n):
f[i]=f[i-1]+1
for j in range(i-1,-1,-1):
if dp[j][i]:
f[i]=min(f[i],f[j-1]+1 if j>=1 else 1)
return f[-1]-1 if dp[0][n-1]!=True else 0
java 解法, 执行用时: 54 ms, 内存消耗: 43.4 MB, 提交时间: 2023-01-12 09:52:01
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];
}
}