题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

样例

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

算法分析

• 1、先预处理g[][]数组，g[j][i]表示字符串[j,i]的子字符串是一个回文串
• 2、分割多少次 等价于 分成多少部分 - 1
• 3、如图所示
  
• 4、结果：f[n] - 1

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public int minCut(String s) {
        int n = s.length();
        s = " " + s;
        boolean[][] g = new boolean[n + 1][n + 1];
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= i;j ++)
            {
                if(i == j) g[j][i] = true;
                else if(s.charAt(i) == s.charAt(j) && (i - 1 < j + 1 || g[j + 1][i - 1]))
                    g[j][i] = true;
            }

        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= i;j ++)
            {
                if(g[j][i]) f[i] = Math.min(f[i], f[j - 1] + 1);
            }

        return f[n] - 1;
    }
}