问题背景

给你一个字符串 $s$，如果可以将它分割成三个 非空 回文子字符串，那么返回 $true$，否则返回 $false$。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

数据约束

• $3\le s.length\le 2000$
• $s$ 只包含小写英文字母。

解题过程

约束了分割的次数，可以看作 分割回文串 III 的一种特殊情形，再写一次同样的代码当作练习。
单纯考虑这个问题本身，实际上分割成三个字符串，暴力解也只需要嵌套两层循环，时间方面的性能会比回溯好很多。

具体实现

class Solution {public boolean checkPartitioning(String s) {return palindromePatition(s, 3) == 0;}private int palindromePatition(String s, int k) {int n = s.length();int[][] changeMemo = new int[n][n];for (int[] row : changeMemo) {Arrays.fill(row, -1);}int[][] dfsMemo = new int[k][n];for (int[] row : dfsMemo) {Arrays.fill(row, -1);}return dfs(k - 1, n - 1, s.toCharArray(), dfsMemo, changeMemo);}private int dfs(int i, int right, char[] chS, int[][] dfsMemo, int[][] changeMemo) {if (i == 0) {return minChange(0, right, chS, changeMemo);}if (dfsMemo[i][right] != -1) {return dfsMemo[i][right];}int res = Integer.MAX_VALUE;for (int left = i; left <= right; left++) {res = Math.min(res, dfs(i - 1, left - 1, chS, dfsMemo, changeMemo) + minChange(left, right, chS, changeMemo));}return dfsMemo[i][right] = res;}private int minChange(int i, int j, char[] chS, int[][] changeMemo) {if (i >= j) {return 0;}if (changeMemo[i][j] != -1) {return changeMemo[i][j];}int res = minChange(i + 1, j - 1, chS, changeMemo);if (chS[i]  != chS[j]) {res++;}return changeMemo[i][j] = res;}
}