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

问题背景

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

数据约束 1 ≤ s . l e n g t h ≤ 2000 1 \le s.length \le 2000 1≤s.length≤2000 s s 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; } }