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.

题意同样简单明了。

解法：

由上题Palindrome Partitioning，可以得到一个解此题的思路，DFS穷举所有方案。然而，仅仅是DFS会超时。此题仅要求求得划分次数最小的方法的划分次数。在这个问题下，dfs(string &s, int idx) 返回 s[idx, s.size()-1] 这个子串最少需要多少次划分。可以发现，朴素DFS存在大量的重复计算，因为s[0, idx)子串有多少种划分法，dfs(string &s, int idx) 就会被调用多少次，而每次计算 dfs(string &s, int idx) 返回的结果都是相同的。因此，自然而然的想到记忆化搜索，也就是dp。

class Solution {

public:

    vector<vector<bool>> is_palindrome;

    vector<int> dp;

    int minCut(string s) {

        int len = s.size();

        is_palindrome = std::move(vector<vector<bool>>(len, vector<bool>(len, false)));

        dp = std::move(vector<int>(len, len+));

        for(size_t l=; l<=len; l++)

            for(size_t head=; head+l-<len; head++){

                int tail = head+l-;

                if(l == )

                    is_palindrome[head][tail] = true;

                else if(s[head]==s[tail] && (head == tail- || is_palindrome[head+][tail-]))

                    is_palindrome[head][tail] = true;

            }

        int ret = len;

        dfs(s, );

        return dp[]-;

    }

    int dfs(string& s, int hp){

        if(hp == s.size())

            return ;

        if(dp[hp] < s.size()+)

            return dp[hp];

        int ret = s.size()+;

        for(size_t i=s.size()-hp; i>=; i--)

            if(is_palindrome[hp][hp+i-])

                ret = min(ret, +dfs(s, hp+i));

        return dp[hp] = ret;

    }

};

巴特西

Leetcode_132. Palindrome Partitioning II_[DP]

最新文章

热门文章