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

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

示例 1：

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

示例 2：

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

提示：

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

解法

思路和算法

用 n 表示字符串 s 的长度。将字符串 s 分割成三个子串的方案数是 \dfrac{(n - 1)(n - 2)}{2，如果对于每种分割方案使用 O(n) 的时间判断三个子串是否都是回文子串，则时间复杂度是 O(n^3)，该时间复杂度过高，需要优化。

为了降低时间复杂度，对于每种分割方案应使用 O(1) 的时间判断三个子串是否都是回文子串，因此需要预计算字符串 s 的每个子串是否为回文子串。以下将字符串 s 的回文子串对应的下标区间称为回文区间。

用 n 表示字符串 s 的长度。对于 0 \le i < j < n 且 j - i > 2，区间 [i, j] 和区间 [i + 1, j - 1] 的中心位置相同，如果满足 s[i] = s[j] 且区间 [i + 1, j - 1] 是回文区间，则区间 [i, j] 也是回文区间，否则区间 [i, j] 不是回文区间。可以使用动态规划预计算每个区间是否为回文区间。

创建 n \times n 的二维数组 isPalindrome，其中 isPalindrome}[i][j] 表示区间 [i, j] 是否为回文区间。

对于长度为 1 或 2 的区间，可以直接判断是否为回文区间，因此动态规划的边界情况如下。

当 j = i 时，区间长度为 1，一定是回文区间，因此对于任意 0 \le i < n，isPalindrome}[i][i] = \text{true。
当 j - i = 1 时，区间长度为 2，如果两个字符相等则是回文区间，如果两个字符不相等则不是回文区间，因此对于任意 0 \le i < n - 1，如果 s[i] = s[i + 1] 则 isPalindrome}[i][i + 1] = \text{true，如果 s[i] \ne s[i + 1] 则 isPalindrome}[i][i + 1] = \text{false。

当 j - i > 1 时，区间长度至少为 3，去掉区间 [i, j] 的首尾字符之后剩余的区间 [i + 1, j - 1] 非空，可以根据 s[i] 是否等于 s[j] 和区间 [i + 1, j - 1] 是否为回文区间判断区间 [i, j] 是否为回文区间。因此动态规划的状态转移方程是 isPalindrome}[i][j] = (s[i] = s[j]) & \textit{isPalindrome}[i + 1][j - 1]。

根据动态规划的状态转移方程，计算 isPalindrome}[i][j] 需要使用 isPalindrome}[i + 1][j - 1] 的值，即区间 [i + 1, j - 1] 的状态值需要在区间 [i, j] 的状态值之前计算。由于区间 [i + 1, j - 1] 和区间 [i, j] 相比，区间长度更小且区间开始下标更大，因此计算 isPalindrome}[i][j] 的顺序可以是以下两种。

从小到大遍历每个区间长度，对于每个区间长度依次计算每个区间的状态值。
从大到小遍历每个区间开始下标 i，对于每个区间开始下标 i 从小到大遍历每个区间结束下标 j，依次计算每个区间 [i, j] 的状态值。

遍历所有的区间之后，即可知道每个区间是否为回文区间。

预计算之后，根据预计算的结果判断是否存在将字符串 s 分割成三个回文子串的方案。

对于满足 0 < i < j < n 的每个下标对 (i, j)，可以将字符串 s 分成下标范围 [0, i - 1]、[i, j - 1] 和 [j, n - 1] 的三个子串，每个子串的长度不小于 1。如果存在一个下标对 (i, j) 满足 isPalindrome}[0][i - 1] = \textit{isPalindrome}[i][j - 1] = \textit{isPalindrome}[j][n - 1] = \text{true，则字符串 s 的下标范围 [0, i - 1]、[i, j - 1] 和 [j, n - 1] 的三个子串都是回文子串，返回 true。如果不存在符合要求的下标对 (i, j)，则返回 false。

由于已经预计算 isPalindrome 的结果，因此时间复杂度是 O(n^2)，低于 O(n^3)。

实现方面，如果下标 i 对应的 isPalindrome}[0][i - 1] 的值为 false 则可以跳过该下标 i，不需要对于该下标 i 遍历每个下标 j。

代码

下面的代码为按照区间长度递增顺序预计算的实现。

[sol1_1-Java]class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int subLength = 3; subLength <= n; subLength++) {
            for (int i = 0, j = subLength - 1; j < n; i++, j++) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (isPalindrome[0][i - 1]) {
                for (int j = i + 1; j < n; j++) {
                    if (isPalindrome[i][j - 1] && isPalindrome[j][n - 1]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

[sol1_1-C#]public class Solution {
    public bool CheckPartitioning(string s) {
        int n = s.Length;
        bool[][] isPalindrome = new bool[n][];
        for (int i = 0; i < n; i++) {
            isPalindrome[i] = new bool[n];
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = s[i] == s[i + 1];
        }
        for (int subLength = 3; subLength <= n; subLength++) {
            for (int i = 0, j = subLength - 1; j < n; i++, j++) {
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i + 1][j - 1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (isPalindrome[0][i - 1]) {
                for (int j = i + 1; j < n; j++) {
                    if (isPalindrome[i][j - 1] && isPalindrome[j][n - 1]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

下面的代码为按照区间开始下标递减顺序预计算的实现。

[sol1_2-Java]class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (isPalindrome[0][i - 1]) {
                for (int j = i + 1; j < n; j++) {
                    if (isPalindrome[i][j - 1] && isPalindrome[j][n - 1]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

[sol1_2-C#]public class Solution {
    public bool CheckPartitioning(string s) {
        int n = s.Length;
        bool[][] isPalindrome = new bool[n][];
        for (int i = 0; i < n; i++) {
            isPalindrome[i] = new bool[n];
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = s[i] == s[i + 1];
        }
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i + 1][j - 1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (isPalindrome[0][i - 1]) {
                for (int j = i + 1; j < n; j++) {
                    if (isPalindrome[i][j - 1] && isPalindrome[j][n - 1]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。预计算的状态数是 O(n^2)，每个状态的计算时间是 O(1)，时间复杂度是 O(n^2)；计算是否存在分割成三个回文子串的方案需要遍历的下标对数量是 O(n^2)，每个下标对的判断时间是 O(1)，时间复杂度是 O(n^2)。
空间复杂度：O(n^2)，其中 n 是字符串 s 的长度。预计算需要创建大小为 n \times n 的二维数组。

1745-分割回文串 IV

解法

思路和算法

代码

复杂度分析