LeetCode——回文串分割IV

题目描述

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为回文字符串。

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

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

提示：

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

题解

• 将字符串分割成三个非空子字符串，判断是否是回文字符串。

• 时间复杂度：O(n^3^)，超时

  class Solution {
    public boolean checkPartitioning(String s) {
        char[]chars=s.toCharArray();
        for(int i=0;i<chars.length-2;++i){
            for(int j=i+1;j<chars.length-1;++j){
                if(isHuiWen(chars,0,i)&&isHuiWen(chars,i+1,j)&&isHuiWen(chars,j+1,chars.length-1)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean isHuiWen(char[]chars,int left,int right){
        while(left<right){
            if(chars[left]==chars[right]){
                ++left;
                --right;
            }else{
                return false;
            }
        }
        return true;
    }
  }

• 优化：首先找出所有回文子字符串的位置，避免重复判断。

  • 每单个字符为一个回文子字符串。

  • 以单个字符为中心，向两边扩展，寻找长度为奇数的回文子字符串。

  • 以单个字符为左端点，向两边扩展，寻找长度为偶数的回文子字符串。

  • 时间复杂度：O(n^2^)。

    class Solution {
    public boolean checkPartitioning(String s) {
      char[]chars=s.toCharArray();
    
      boolean[][]dp=new boolean[chars.length][chars.length];
      for(int i=0;i<chars.length;++i){
          dp[i][i]=true;
          // 奇数
          for(int left=i-1,right=i+1;left>=0&&right<chars.length;--left,++right){
              if(chars[left]==chars[right]){
                  dp[left][right]=true;
              }else{
                  break;
              }
          }
          // 偶数
          for(int left=i,right=i+1;left>=0&&right<chars.length;--left,++right){
              if(chars[left]==chars[right]){
                  dp[left][right]=true;
              }else{
                  break;
              }
          }
      }
    
      for(int i=0;i<chars.length-2;++i){
          for(int j=i+1;j<chars.length-1;++j){
              if(dp[0][i]&&dp[i+1][j]&&dp[j+1][chars.length-1]){
                  return true;
              }
          }
      }
      return false;
    }
    }