8ms cpp solution with o(n) space complexity


  • 0
    class Solution {
    public:
        int minCut(string s) {
            if(s=="") return 0;
            int sz = s.size(), i = 0;
            vector<int> dp(sz+1,INT_MAX);
            dp[0] = 0;
            while(i<sz){
                int j = i;
                while(j+1<sz&&s[j+1]==s[i]) j++;
                for(int k = i; k <=j; k ++){
                    for(int m = k; m <=j; m++){
                        dp[m+1] = min(dp[m+1], dp[k]+1);
                    }
                }
                int l = i-1, r = j+1;
                while(l>=0&&r<sz&&s[l]==s[r]) {
                    r++;
                    dp[r] = min(dp[r], dp[l--]+1);
                }
                i = j+1;
            }
            return dp[sz]-1;
        }
    };
    
    1. Use dp[i] (i>0) to record minimal palindrome partitions of substring 0 to i-1.
    2. From middle to two sides to find a palindrome, which is more efficient. Once find a palindrome, update dp.

Log in to reply
 

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