每日一练：分割回文串Ⅳ

1745. 分割回文串 IV - 力扣（LeetCode）

题目要求：

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

• 3 <= s.length <= 2000
• s​​​​​​ 只包含小写英文字母。

解法-1 动态规划 O(N^2)：

        要分成三个回文子串，首先要把字符串分割成三个部分：

        

        只要s[j]到s[i]是回文串，并且s[0]到s[j-1]、s[i+1]到s[n-1]也是回文串，那它就可以分割成三个回文串。 

        这个题也需要创建一个二维dp表，dp[i][j]存放以s[j]为开头，以s[i]为结尾的子串是不是回文串，填表方法与每日一练：回文子串-CSDN博客一致。

        填完表后，遍历dp表，只要某个dp[i][j]符合：dp[i][j] && dp[n-1][i+1] && dp[j-1][0]，那么就返回true，遍历完之后还没有返回true，说明它不能分割成三个回文子串，就返回false。

        注意，最后遍历dp表时，i、j从1开始遍历，到n-2结束，防止出现以下情况：

        

        它只分成了两端，不符合题目要求。

class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n);for(int i = 0;i < n;i++)dp[i].resize(i+1);for(int i = 0;i < n;i++){for(int j = 0;j <= i;j++){if(s[j] == s[i]){if(i == j)dp[i][j] = true;else if(j == i-1)dp[i][j] = true;elsedp[i][j] = dp[i-1][j+1];}}}for(int i = 1;i < n-1;i++){for(int j = 1;j <= i;j++){if(dp[i][j]){if(dp[n-1][i+1] && dp[j-1][0])return true;}}}return false;}
};