O(n^2) c++ solution / trying to improve the runtime a bit


  • 0
    P
    class Solution {
    public:
        int minCut(string s) {
            int n = s.size();
            vector<vector<bool> > dp;
            for (int i = 0; i < n; ++i) {
                dp.push_back(vector<bool>(n,false));
                dp[i][i] = true;
            }
            
            for (int i = 0; i < n-1; ++i) {
                dp[i][i+1] = s[i]==s[i+1];
            }
            
            for (int l = 3; l <= n; ++l) {
                for (int i = 0; i <= n-l; ++i) {
                    int j = i+l-1;
                    dp[i][j] = s[i]==s[j] && dp[i+1][j-1];
                }
            }
            
            if (dp[0][n-1]) return 0;
            vector<int> cuts(n,INT_MAX);
            for (int i = 0; i < n; ++i) {
                if (dp[0][i]) {
                    cuts[i] = 0;
                } else {
                    for (int k = i-1; k >= 0 && cuts[i] > 1; --k) {
                        if (cuts[k] != INT_MAX && dp[k+1][i]) {
                            cuts[i] = min(cuts[i],cuts[k]+1);
                        }
                    }
                }
            }
            return cuts[n-1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.