Description

Given a strings, cut_s_into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example

Given s ="aab",

Return 1since the palindrome partitioning ["aa", "b"] could be produced using _1 _cut.

Solution

注意初始状态dp[0] = -1而不是0.因为本身就是palindrome的string是0 cut的

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    public int minCut(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }

        int[] dp = new int[s.length() + 1];
        dp[0] = -1;
        for (int i = 2; i <= s.length(); i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isPartition(s, j, i - 1)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[s.length()];
    }

    private boolean isPartition(String s, int start, int end) {
        if (start >= end)  {
            return true;
        }

        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }

        return isPartition(s, start + 1, end - 1);
    }
};