132. Palindrome Partitioning II

Bertha 。 2022-02-15 13:41 163阅读 0赞

Given a string s, partition s such that every substring of the partition is a palindrome.
    
    Return the minimum cuts needed for a palindrome partitioning of s.
    
    Example:
    
    Input: "aab"
    Output: 1
    Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

本题可以看成一个动态规划题目。有以下两点可作为递推条件（cut\[i\]表示s.subString(0, i+1)满足题意的分割次数）：

1，cut\[i\]的值为当0 <= j <= i时，cut\[j\]的最小值加1。

2，如果s.subString(j, i+1)是回文字符串且s.charAt(j-1)==s.charAt(i+1)，则s.subString(j-1, i+2)也是回文字符串。

public int minCut(String s) {
            char[] c = s.toCharArray();
            int n = c.length;
            int[] cut = new int[n];//cut[i]表示s.subString[i]达到题目要求的最小分割次数
            boolean[][] isPalinized = new boolean[n][n];//isPalinized[i][j]判断c[i]...c[j]组成的字符串是否是回文字符串
    
            for(int i = 0; i < n; ++i) {
                int min = i;//min等会赋值给cut[i]，此时最大分割次数为i次
                for(int j = 0; j <= i; ++j) {
                    if(c[j] == c[i] && (j + 1 > i - 1/**表示j + 1 == i这种情况**/ || isPalinized[j+1][i-1])) {
                        isPalinized[j][i] = true;
                        min = j == 0 ? 0/**表示s.subString(0, i+1)是回文的，即0次分割就能达到题目要求**/ : Math.min(min, cut[j-1] + 1/**s.subString(0, i+1)中，s.subString(j, i+1)是回文字符串所以此次结果为cut[j-1]+1**/)/**如上所说，min要赋值给cut[i]，所以对所有情况，更新min**/;
                    }
                }
                cut[i] = min;
            }
    
            return cut[n-1];
        }