题目要判断一个字符串能不能被分割成3个回文串。分析了一下这道题大概率是动态规划，字符串的最大长度是2000，这个量级的数据规模应该能用$\mathcal{O}(n^2)$的时间复杂度通过，但是不要管那么多，先用简单暴力的方法试试，万一通过了呢？（不能这样想啊，毕竟刷LeetCode是要认真的）。
一个字符串，拆成3部分，有两个断点$i, j$，每组$(i, j)$的循环里，要判断3个子字符串是不是回文，3个子字符串的长度和是整个字符串的长度，时间复杂度是$\mathcal{O}(n^3)$，但是有剪枝，有通过的可能（侥幸心理）…… 。超时了。超时代码放在最后面，我提交的时候，一共有84的测试案例，在第80个案例超时，代码应该是正确的。
在已有的思路上继续分析，我们希望在$\mathcal{O}(n^2)$时间内解决，$n^2$是两重循环，即找到两个断点的时间消耗，这里是无法优化的。毕竟要找到这样的两个点没有任何规律可言，只能两重循环。那么就只能优化每组$(i, j)$内判断回文的操作了。这步操作的时间消耗，必须降到$\mathcal{O}(1)$。
整理一下思路：将任意一个子字符串是否是回文的操作先做完，这样时间复杂度就从$n * n * n = \mathcal{O}(n^3)$ 降到 $n * n + n * n * 1 = \mathcal{O}(n^2)$。
我们用动态规划的方法来计算任意一个子串是否回文。DP[i][j]表示以i为起点，j为终点的字串的回文情况，那么DP[i][j] = DP[i + 1][j - i] && s[i] == s[j]
static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
public:
bool checkPartitioning(string s) {
const int n = s.size();
vector<vector<bool>> dp (n, vector<bool> (n, true));
for (int l = 2; l < n; ++l) // l: length of each sub string
for (int i = 0, j = i + l - 1; j < n; ++i, ++j)
dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);
for (int i = 0, n = s.size() - 1; i < n; ++i) // n means last index in the folling loops
for (int j = i + 1; j < n; ++j)
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n])
return true;
return false;
}
};
超时代码
static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
// *** | **** | **** ==> [0, i], [i + 1, j], [j + 1, n], string length: n + 1
// "abcbdd" ==> i = 0, j = 3
class Solution_TLE {
public:
bool checkPartitioning(string s) {
auto isPalindrome = [&] (int l, int r) {
if (l > r) return false;
while (l < r) {
if (s[l] != s[r]) return false;
++l;
--r;
}
return true;
};
for (int i = 0, n = s.size() - 1; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (isPalindrome(0, i) && isPalindrome(i + 1, j) && isPalindrome(j + 1, n))
return true;
return false;
}
};