题目描述

给你一个字符串 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;
      }
      }