Leetcode 132.Palindrome Partitioning II 题解

题目链接

Leetcode 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.

Example:

Input: "aab"

Output: 1

Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

解题思路

选择这题是因为想练习一下这周学习到的dp算法，分析完这个题目，我们可以想出状态转移方程如下:

if isReverse(str.substr(0,i)):
    dp[i] = 0

# defalut dp[i] = i-1 因为最多分割i-1次
if isReverse(str.substr(j,i-j)):
    dp[i] = min(dp[i], dp[j] + 1)
if not isReverse(str.substr(j, i-j))
    dp[i] = min(dp[i], dp[j] + i - j) # j到i最多分割i-j次

但是提交之后虽然正确，但是detail显示时间复杂度不够好

后来看了看别人的做法，发现其实还可以优化一下我们的状态转移方程,基本思路大致相同 ，都是通过检验是否回文码来算dp[i], 不过他通过在i处左右两端同时延伸的同时，随便检验是否回文，同时计算min(dp[i+len+1], dp[i-len]+1) 和 dp[i+len+2] = min(dp[i+len+2], dp[i-len]+1)。这样免去了我们之前在(0, i)的不是回文码的时候对于每个str(j, i-j)的回文码检验，大大减少了时间复杂度。

题目代码

一开始的做法

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        dp[0] = 0; // 初始化
        for(int i = 1; i <= n; i++){
            if (isReverseStr(s.substr(0, i))){
                dp[i] = 0;
                continue;
            }

            dp[i] = i-1;

            for (int j = 1; j < i; j++) {
                if (isReverseStr(s.substr(j, i-j)))
                    dp[i] = min(dp[i], dp[j] + 1);
                else
                    dp[i] = min(dp[i], dp[j] + i - j);
            }
        }
        return dp[n];
    }

    bool isReverseStr(string s) {
        int size = s.size();
        for (int i = 0; i <= (size-1)/2; i++) {
            if (s[i] != s[size-i-1])
                return false;
        }
        return true;
    }
};

后面的做法

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n+1, n-1);
        dp[0] = -1;       //act as a sentinel
        for(int i = 0; i < n; i++){
    //palindrome of length 1,3,5...
            for(int len = 0; i-len >= 0 && i+len < n && s[i-len] == s[i+len]; len++)
                dp[i+len+1] = min(dp[i+len+1], dp[i-len]+1);
    //palindrome of lenght 2,4,6...
            for(int len = 0; i-len >= 0 && i+len+1 < n && s[i-len] == s[i+len+1]; len++)
                dp[i+len+2] = min(dp[i+len+2], dp[i-len]+1);
        }
        return dp[n];
    }
};