132.Palindrome Partitioning II¶

132.Palindrome Partitioning II¶

Tags: Hard Dynamic Programming

Links: https://leetcode.com/problems/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.

这道题和前面的那道题相比，问的是最少需要分隔的次数，当然可以继续利用上一题的方法，当pos到了字符串末尾的时候，分隔的次数就是数组的长度减1，但是这种做法会超时，比如下面这个测试用例：

"ababababababababababababcbabababababababababababa"

注意：下面的代码会超时

class Solution {
public:
    int minCut(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!s.size()) return 0;
        vector<string> tmp;
        int res = s.size();
        DFS(s, 0, tmp, res);

        return res;
    }

    void DFS(const string & s, int pos, vector<string> & tmp, int & res)
    {
        if (pos == s.size()) { res = min(res, (int)tmp.size() - 1); return; }

        for (int i = pos; i < s.size(); ++i) {
            if (!isPalindrome(s, pos, i)) continue;
            tmp.push_back(s.substr(pos, i - pos + 1));
            DFS(s, i + 1, tmp, res);
            tmp.pop_back();
        }
    }

    bool isPalindrome(const string & s, int left, int right)
    {
        while (left < right) {
            if (s[left++] != s[right--]) return false;            
        }

        return true;
    }
};

进而想可以用动态规划来解决，用d[i]代表将字符串的前i个字符分割成回文串的最小操作数。一个字符串最多就是分成n - 1个，也就是每个字符单独最为一个字符串。那么接下来就是去确定状态转移方程。当前的字符可能和前面的字符串构成回文，没有经过优化的就是每次去判断位于区间i, j的字符串是否是回文，那么这样会存在很多的重复计算，可以用一个二维数组记录从i,j内的字符串是否是回文。

没有优化的版本（1676ms）

class Solution {
public:
    int minCut(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size(); if (!n) return 0;
        vector<int> d(n + 1, n);
        d[0] = -1;
        d[1] = 0;
        for (int i = 2; i <= n; ++i) {
            for (int j = i; j >= 1; --j) {
                if (!isPalindrome(s, j - 1, i - 1)) continue;
                d[i] = min(d[i], d[j - 1] + 1);
            }
        }

        return d[n];
    }

    bool isPalindrome(const string & s, int left, int right)
    {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};

经过二维数组优化（优化后时间立刻减少到68ms）

class Solution {
public:
    int minCut(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size(); if (!n) return 0;
        vector<int> d(n + 1, n);
        vector<vector<bool>> isPalindrome(n + 1, vector<bool>(n + 1, false));
        isPalindrome[1][1] = true;
        d[0] = -1, d[1] = 0; 

        for (int j = 2; j <= n; ++j) {
            for (int i = j; i >= 1; --i) {
                if (s[i - 1] == s[j - 1] && (j - i < 2 || isPalindrome[i + 1][j - 1])) {
                    isPalindrome[i][j] = true;
                    d[j] = min(d[j], d[i - 1] + 1);
                }
            }
        }

        return d[n];
    }
};