其他
570，动态规划解回文串分割 IV
I am not afraid of storms,for I am learning how to sail my ship.
我不害怕风暴, 因为我正在学习如何乘风破浪。
问题描述
来源：LeetCode第1745题
难度：困难
给你一个字符串s，如果可以将它分割成三个非空回文子字符串，那么返回true，否则返回false。
当一个字符串正着读和反着读是一模一样的，就称其为回文字符串。
示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000
s 只包含小写英文字母。
动态规划解决
这题要求能不能把字符串s分隔成3个非空的回文子串。最简单的一种方式就是把字符串分隔成3个子串，然后再判他们是否都是回文的，如果是则返回true，如果不是则继续分隔然后接着在判断……直到不能分隔为止，我们随便举个例子画个图看一下。
大致代码如下
1public boolean checkPartitioning(String s) {
2 for (int i = 0; i < s.length(); i++) {
3 for (int j = i + 1; j < s.length() - 1; j++) {
4 //截取字符串[0,i]
5 String str1 = s.substring(0, i + 1);
6 //截取字符串[i+1,j]
7 String str2 = s.substring(i + 1, j + 1);
8 //截取字符串[j+1,s.length()-1]
9 String str3 = s.substring(j + 1, s.length());
10 //把字符串s截取3段，判断每段是否都是回文的
11 if (isPalindrome(str1) && isPalindrome(str2) && isPalindrome(str3))
12 return true;
13 }
14 }
15 return false;
16}
如果字符串s比较短的话，上面代码是没有问题的，但如果字符串s比较长，很容易超时。
我们可以先计算字符串s的所有子串中哪些是回文的，哪些不是，然后再判断。关于计算方式在《540，动态规划和中心扩散法解回文子串》中有详细介绍，除此之外还可有看下
这里就不在重复介绍。我们来直接看下代码
1public boolean checkPartitioning(String s) {
2 int length = s.length();
3 //dp[i][j]：表示字符串s从下标i到j是否是回文串
4 boolean[][] dp = new boolean[length][length];
5 for (int i = length - 1; i >= 0; i--) {
6 for (int j = i; j < length; j++) {
7 //如果i和j指向的字符不一样，那么dp[i][j]就
8 //不能构成回文字符串
9 if (s.charAt(i) != s.charAt(j))
10 continue;
11 dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
12 }
13 }
14
15 //然后再截取3段，判断这3段是否都是回文的
16 for (int i = 0; i < length; i++) {
17 for (int j = i + 1; j < length - 1; j++) {
18 if (dp[0][i] && dp[i + 1][j] && dp[j + 1][length - 1])
19 return true;
20 }
21 }
22 return false;
23}
24
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。