LeetCode 132. 分割回文串 II

Categories:

题目描述
思路分析
1. 解法一：回文预处理 + 最小切割 DP（推荐）
相似题目

题目描述

✅ 132. 分割回文串 II

思路分析

解法一：回文预处理 + 最小切割 DP（推荐）

核心思路：

先预处理 pal[i][j] 表示 s[i..j] 是否回文。

设 dp[i] 表示 s[0..i] 的最小切割次数。

若 pal[0][i] 为真，则 dp[i]=0；否则枚举切点 j，若 pal[j+1][i] 为真，则 dp[i]=min(dp[i], dp[j]+1)。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示字符串长度。

空间复杂度：O(n^2)。

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || pal[i + 1][j - 1])) {
                    pal[i][j] = true;
                }
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (pal[0][i]) {
                dp[i] = 0;
                continue;
            }
            dp[i] = i;
            for (int j = 0; j < i; j++) {
                if (pal[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

func minCut(s string) int {
	n := len(s)
	pal := make([][]bool, n)
	for i := range pal {
		pal[i] = make([]bool, n)
	}

	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] && (j-i <= 2 || pal[i+1][j-1]) {
				pal[i][j] = true
			}
		}
	}

	dp := make([]int, n)
	for i := 0; i < n; i++ {
		if pal[0][i] {
			dp[i] = 0
			continue
		}
		dp[i] = i
		for j := 0; j < i; j++ {
			if pal[j+1][i] {
				if dp[j]+1 < dp[i] {
					dp[i] = dp[j] + 1
				}
			}
		}
	}

	return dp[n-1]
}

相似题目

题目	难度	考察点
131. 分割回文串	中等	回溯、DP
132. 分割回文串 II	困难	DP
5. 最长回文子串	中等	DP/双指针
647. 回文子串	中等	DP/中心扩展
516. 最长回文子序列	中等	DP
214. 最短回文串	困难	字符串、KMP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/17499975