Leetcode 1278: Palindrome Partitioning III

https://leetcode.com/problems/palindrome-partitioning-iii/description/

Notes:

This question is a typical dfs question, and can be optimized by memorization.

We need to continuously cut the original string into K pieces. Let say the size of the string is N, and N >= K.

If we cut at the position of the first char, then the remaining string needs to be cut into (K-1) pieces.

Now it is clear that this question becomes the same question but with a smaller size. So we can solve it recursively, or by dfs.

And also, the key parameters are the length of the string and the number of pieces to be cut.

If we use the index of the string to label the position of the starting point, then the two key parameters can be labeled as i and K.

What we need to find is memo(0, K), representing the minimum operations needed.

Once we make one cut at position i, then the total operations for this way is Operation to make string from 0 to i becomes palindrome + memo(i+1, K-1).

It is relative straightforward to find how many operation needed to make a string in palindrome.

So memo(0, K) is the smallest value from all possible cuts.

Thus, this question can be solved by dfs + memorization. (So it can also be solved by dp, which is equivalent)

So the TC of this question is O(N/K * N * K) ~ O(N^2), and SC is O(N*K).

See the code below:

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> memo(n, vector<int>(k+1, -1));
        return dfs(s, 0, k, memo);
    }

private:
    int dfs(string &s, int i, int ct, vector<vector<int>> &memo) {
        if(s.size() == ct || i==s.size()) return 0;
        if(ct == 1) return find(s, i, s.size()-1);
        if(memo[i][ct] != -1) return memo[i][ct];
        int t = s.size();
        for(int j=1; i+j-1+ct<=s.size(); ++j) {
            int one = find(s, i, i+j-1);
            t = min(t, one + dfs(s, i+j, ct-1, memo));
        }
        return memo[i][ct] = t;
    }
    int find(string& s, int i, int j) {
        int res = 0;
        while(i<j) {
            if(s[i++] != s[j--]) ++res;
        }
        return res;
    }
};