分割回文串 II

/*
 * 题目思路：
 * 1. 定义一个dp数组，其中dp[i]表示字符串s[0...i]的最少分割次数。
 * 2. 初始化dp数组为最大值，除了dp[0]为0，因为单个字符本身就是回文串。
 * 3. 使用Java Stream API实现内层循环，判断s[j...i]是否是回文串，并更新dp[i]。
 * 4. 返回dp[n-1]的值，即字符串s的最少分割次数。
 */
import java.util.stream.IntStream;
 
public class PalindromePartitioningStream {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            final int finalI = i;
            dp[i] = IntStream.rangeClosed(0, i).filter(j -> s.charAt(finalI) == s.charAt(j) && (finalI - j <= 2 || isPalindrome[j + 1][finalI - 1]))
                .peek(j -> isPalindrome[j][finalI] = true)
                .map(j -> j == 0 ? 0 : dp[j - 1] + 1)
                .min().orElse(i);
        }
        return dp[n - 1];
    }
}