【Leetcode 每日一题】132. 分割回文串 II

问题背景

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

数据约束

• $1\le s.length\le 2000$
• $s$ 仅由小写英文字母组成

解题过程

一开始的想法是在 分割回文串 的基础上加一个计算列表长度最大值，然后就遇到了少见的空间不足。
实际上判断回文和计算最少分割次数，都可以用动态规划的思想来考虑，两个过程都会涉及到大量的重复计算，不做记忆化肯定是会出问题的。

具体实现

class Solution {
    public int minCut(String s) {
        char[]  chS = s.toCharArray();
        int n = chS.length;
        int[][] palMemo = new int[n][n];
        for (int[] row : palMemo) {
            Arrays.fill(row, -1);
        }
        int[] dfsMemo = new int[n];
        Arrays.fill(dfsMemo, -1);
        return dfs(n - 1, chS, palMemo, dfsMemo);
    }

    private int dfs(int right, char[] chS, int[][] palMemo, int[] dfsMemo) {
        if (isPalindrome(0, right, chS, palMemo)) {
            return 0;
        }
        if (dfsMemo[right] != -1) {
            return dfsMemo[right];
        }
        int res = Integer.MAX_VALUE;
        for (int left = 1; left <= right; left++) {
            if (isPalindrome(left, right, chS, palMemo)) {
                res = Math.min(res, dfs(left - 1, chS, palMemo, dfsMemo) + 1);
            }
        }
        return dfsMemo[right] = res;
    }

    private boolean isPalindrome(int left, int right, char[] chS, int[][] palMemo) {
        if (left >= right) {
            return true;
        }
        if (palMemo[left][right] != -1) {
            return palMemo[left][right] == 1;
        }
        boolean res = chS[left] == chS[right] && isPalindrome(left + 1, right - 1, chS, palMemo);
        palMemo[left][right] = res ? 1 : 0;
        return res;
    }
}