1745. 分割回文串IVJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

示例 1：

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

示例 2：

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

提示：

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

# 思路

boolean[][] dp

# 解法

class Solution {
    public boolean checkPartitioning(String s) {
        int sLen = s.length();
        boolean[][] dp = new boolean[sLen][sLen];//dp[i][j]为s[i~j]是否为回文
        dp[0][0] = true;
        for(int i = 1; i < sLen; i++){
            dp[i][i] = true;
            dp[i - 1][i] = s.charAt(i) == s.charAt(i - 1)? true: false;
        }
        for(int len = 3; len <= sLen; len++){
            for(int i = 0; i + len <= sLen; i++){
                int j = i + len - 1;
                if(dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) dp[i][j] = true;
            }
        }

        //开始找是否能分成三个回文子串，即能否找到两个分割点
        for(int spOne = 0; spOne + 2 < sLen; spOne++){
            for(int spTwo = spOne + 1; spTwo + 1 < sLen; spTwo++){
                if(dp[0][spOne] && dp[spOne + 1][spTwo] && dp[spTwo + 1][sLen - 1]) return true;
            }
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 总结

分析出几种情况，然后分别对各个情况实现

#Java