🔴 剑指 Offer II 094. 最少回文分割
LeetCode 提示
题目难度 困难
原题链接 🔗 leetcode
#
题解1两部分:
一是如何判断substring回文串?用二维数组做记忆化搜索
二是怎么判断最小分割?用一维数组做动态规划
抄作业
class Solution { public int minCut(String s) { int n = s.length(); boolean[][] pa = new boolean[n][n]; for (int i=0; i<n; i++) { Arrays.fill(pa[i], true); }
for (int i=n-1; i>=0; i--) { for (int j=i+1; j<n; j++) { pa[i][j] = s.charAt(i) == s.charAt(j) && pa[i+1][j-1]; } }
int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i=1; i<n; i++) { if (pa[0][i]) { dp[i] = 0; } else { for (int j=1; j<=i; j++) { if (pa[j][i]) { dp[i] = Math.min(dp[i], dp[j-1]+1); } } } }
return dp[n-1]; }}