leetcode每日一题——1745分割回文串

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

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

示例 1：

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

示例 2：

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

方法一：双指针（超时）

class Solution {public boolean checkPartitioning(String s) {//判断入参if (s.length() == 3) return true;int length = s.length();//解题思路：要求找三个回文字符串，则我们要将原本的字符切割为三份//此时我们可以从左边和右边开始找满足条件的字符串长度，最后在中间如果能找到符合条件的，则返回true，反之返回falseboolean[] leftList = new boolean[length];boolean[] rightList = new boolean[length];for (int i = 0;i < length;i++){leftList[i] = isHW(s.substring(0,i+1));rightList[length - i - 1] = isHW(s.substring(length - i - 1,length));}//双重for循环寻找中间值for(int left = 1;left < length;left++){for (int right = length - 2;right >= 0 && right >= left;right--){//判断不符合条件//left-1不为true//right+1不为trueif (leftList[left - 1] && rightList[right + 1]) {if (isHW(s.substring(left,right+1))) return true;}}}return false;}public boolean isHW(String s) {if (s.length() == 1) return true;char[] chars = s.toCharArray();int left = 0;int right = s.length() - 1;while (left < right) {if (chars[left] != chars[right]) return false;left++;right--;}return true;}
}

结果：

方法二：动态规划

class Solution {public boolean checkPartitioning(String s) {//判断入参if (s.length() == 3) return true;int length = s.length();//解题思路：要求找三个回文字符串，则我们要将原本的字符切割为三份//此时我们可以从左边和右边开始找满足条件的字符串长度，最后在中间如果能找到符合条件的，则返回true，反之返回falseboolean[][] dp = new boolean[length][length];//初始化for (int i = 0;i < length;i++){dp[i][i] = true;}for (int left = 0;left < length;left++){for (int right = left + 1;right < length;right++) {if (s.charAt(right - (left + 1)) == s.charAt(right)){dp[right - (left + 1)][right] = (dp[right - left][right - 1]) || (right - left > right - 1);}}}//循环寻找中间值for(int right = 0;right < length;right++){if (dp[0][right]){for (int left = right + 1;left < length - 1;left++){if (dp[right+1][left] && dp[left+1][length-1]) return true;}}}return false;}
}

结果：