132. Palindrome Partitioning II

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.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

// Solution 1: DP
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length();
        boolean dp[][] = new boolean[len][len];
        int result[] = new int[len];
        for (int i = 0; i < len; i++) {
            result[i] = i;
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 1 || dp[i - 1][j + 1])) {
                    dp[i][j] = true;
                    if (j > 0) {
                        result[i] = Math.min(result[j - 1] + 1, result[i]);
                    } else {
                        result[i] = 0;
                    }
                    
                }
            }
        }
        return result[len - 1];
    }
}
// Solution 2: Similar to Palindrome Partition 1, use backtracking, however, time limited exceeded.
/*
public class Solution {
    
    private int result = Integer.MAX_VALUE;
    
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        dfs(s, 0, -1);
        return result;
    }
    
    public void dfs(String s, int start, int min) {
        if (start == s.length()) {
            result = Math.min(result, min);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                min += 1;
                dfs(s, i + 1, min);
                min -= 1;
            }
        }
    }
    
    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}
*/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s