题目描述

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.

算法

(动态规划) O(n^3)

尼玛，我这样写也过了。。。。。。判断j到i-1之前的子串是否是回文，我用的是遍历求法。而且每换一次划分，就需要重算一个是否回文。感觉之后再做这题，需要优化这个判断回文的复杂度。应该是可以优化到O(n^2)的

Java 代码

class Solution {
    public int minCut(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }

        int n = s.length();
        if (n == 1) {
            return 0;
        }

        // 前i个字符串最少可以划分成dp[i]个回文串
        int dp[] = new int[n + 1];
        dp[0] = 0;

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

        return dp[n] - 1;
    }

    public boolean isPalindrome(String s) {
        int low = 0;
        int high = s.length() - 1;
        //当字符串有奇数个字符时，不用检查中间字符
        while (low < high) {
            if (s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}