132. 分割回文串 II (opens new window)

1.动规+双指针

题目分成两步：

• ①找出所有回文子串。可以使用双指针中心扩散法或动规实现，时间复杂度是O(n平方)
• ②找到最小分割数量。这里有两种思路：
  • 枚举【start，end】之间的切割点，找到最小切割数量。这种方式即使是记忆化搜索也会超时，因为同一个切割点在搜索的过程中会被重复计算多次，尤其是在子串含有多个单字符回文串的情况。比如第i个位置切割的方案和第j个位置切割的方案是相同的( i 不等于 j )，那么就会被重复搜索多次。
  • 固定左端点枚举右端点，每次找出f【0，i】前i个字符串的最小切割数。

class Solution {
    int[][] f;
    public int minCut(String s) {
        f=new int[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            check(s,i-1,i);
            check(s,i,i);
        }
        int[] dp=new int[s.length()];
        for(int i=0;i<s.length();i++){
            if(f[0][i]==1){
                dp[i]=0;
                continue;
            }
            int min=Integer.MAX_VALUE;
            for(int j=1;j<=i;j++){
                if(f[j][i]==1)min=Math.min(min,dp[j-1]+1);
            }
            dp[i]=min;
        }
        return dp[s.length()-1];
    }
    public void check(String s,int ledpt,int right){
        while(ledpt>=0&&right<s.length()){
            if(s.charAt(ledpt)==s.charAt(right)){
                f[ledpt][right]=1;
                ledpt--;
                right++;
            }
            else return;
        }
    }
}