[LeetCode] 132. Palindrome Partitioning II

Posted on | In

Problem

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:

1
2
3
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Explanation

  1. The two dimensional array isPalindrome[i][j] means if the string from character of index i to index j is a palindrome. For example, in the string “abba”, isPalindrome[0][3] will be true because string[0] = string[3] = “a” and isPalindrome[1][2] is true because string[1]=”b” same as string[2]=”b”.

  2. The one dimensional array dp[i] means the length of i (we begin from 0 to i-1) ‘s string’s minimum cut. dp[i] = min(dp[j] + 1) if the string starts from index j to i-1 (we divide the string into str[0:j-1] and str[j:n] the right substring) is palindrome, then the minimum cut of the whole string is equal to the left substring’s minimum cut plus one. We plus one because we need one cut to cut the left substring and right substring.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minCut(String s) {
        int n = s.length();
        if (n <= 1) return 0;
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (i+1 > j-1 || isPalindrome[i+1][j-1])) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (isPalindrome[j][i-1]) {
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }

        return dp[n];
    }
}