132. Palindrome Partitioning II-蒲公英云

132. Palindrome Partitioning II

Bertha 。 2022-02-15 13:41 267阅读 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];
    }