C++ O(N^2) time and O(N^2) space clean DP solution with details


  • 0

    Already see the similar DP solutions posted on the board, here I just add some explanation and comments.

    The DP idea is to calculate min cut of string s based on its prefix substring s.subtr(0, i+1) which ends at index i. Then we scan from right end to left of s.subtr(0, i+1) to search for any palindrome substring inside it so that we can get a candidate partition cut for substring s.subtr(0, i+1). We scan every possible right end palindrome substring to get the minimum cut. Eventually, the result to return is the min cut for s.subtr(0, n) == s.

        int minCut(string s) {
            int n = s.length();
            if (n == 0) return 0;
            
            // minCuts[i]: result for s.substr(0, i+1)
            vector<int> minCuts(n, INT_MAX);
            
            // isPalindrome[i][j]: true if s.substr(i, j-i+1) is palindrome
            vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
            
            minCuts[0] = 0;
            for (int i = 1; i < n; ++i) { // calculate minCuts[i]
                for (int j = i; j >= 0; --j) {
                    // find each palindrome substring ending at index i
                    // find palindrome if two ends identical and internal is palindrome
                    if (s[j] == s[i] && (i-j < 2 || isPalindrome[j+1][i-1])) {
                        isPalindrome[j][i] = true;
                        // entire s.substr(0, i+1) is palindrome
                        if (j == 0) minCuts[i] = 0;
                        // update minCuts[i]
                        else minCuts[i] = min(minCuts[i], 1+minCuts[j-1]);
                    }
                }
            }
            return minCuts[n-1];
        }
    

Log in to reply
 

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