132. Palindrome Partitioning II - cocoder39/coco39_LC GitHub Wiki

132. Palindrome Partitioning II

solution 1: bottom-up check if s[i .. j] is palindrome. check length from 1 to s.length(). O(n ^ 2) time and O(n ^ 2) space. the memory can be optimized in solution 2.

int minCut(string s) {
        int len = s.length();
        //isPal[i][j] == true if s[i .. j] is a palindrome
        vector<vector<bool>> isPal(len, vector<bool>(len));
        //base cases' lengthes are 1 and 2
        // 3 can be reduced to 1, 4 can be reduced to 2
        for (int i = 0; i < len; i++) {
            isPal[i][i] = true;
            if (i + 1 < len) {
                isPal[i][i + 1] = (s[i] == s[i + 1]);
            }
        }
        
        for (int l = 3; l <= len; l++) { //O(n ^ 2)
            for (int i = 0; i + l <= len; i++) {
                int j = i - 1 + l;
                isPal[i][j] = (isPal[i + 1][j - 1] && s[i] == s[j]);
            }
        }
        
        //cut[i] is min cuts between s[0 .. i];
        vector<int> cut(len, INT_MAX);
        for (int i = 0; i < len; i++) { //O(n ^ 2)
            if (isPal[0][i]) {
                cut[i] = 0;
            }
            for (int j = 0; j < i; j++) {
                if (isPal[j + 1][i]) {
                    cut[i] = min(cut[i], cut[j] + 1); 
                } 
            }
        }
        return cut[len - 1];
    }

solution 2: still O(n ^ 2) time, but O(n) memory. unlike solution 1, record palindrome segment, then reduce cuts via records. Solution 2 reduces cuts while checking palindrome. Although still O(n ^ 2), it saves memory for records, thus memory is O(n) for vector cut. Moreover, the pruning strategy is very strict, selecting s[i] or s[i]/s[i - 1] as centers, compare left and right, once left is not same as right, break the inside loop.

tips:

  • initialization: cut[i] is cuts for first i chars. thus cuts for a string with length of 1 is 0, 2 is 1... IMPORTANT, cut[0] is -1. thus if s[0 .. i - 1] is a palindrome, cut[i] can be updated to cut[0] + 1 = 1
int minCut(string s) {
        int len = s.length();
        vector<int> cut(len + 1); //cut[i] is min cuts for first i chars
        for (int i = 0; i <= len; i++) {
            cut[i] = i - 1; 
        }
        
        for (int i = 0; i < len; i++) {
            //s[i] is center, l is length behind s[i]
            for (int l = 0; i + 1 + l <= len && i >= l && s[i + l] == s[i - l]; l++) {
                cut[i + 1 + l] = min(cut[i + 1 + l], cut[i - l] + 1); 
            }   
            //s[i - 1] and s[i] are centers
            for (int l = 0; i + 1 + l <= len && i - 1 >= l && s[i + l] == s[i - 1 - l]; l++) { 
                cut[i + 1 + l] = min(cut[i + 1 + l], cut[i - 1 - l] + 1);
            }
        }
        return cut[len];
    }

Notes 2020:

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        isPalindrome = [[False] * n for i in range(n)]
        
        for i in range(n):
            isPalindrome[i][i] = True
            if i + 1 < n and s[i] == s[i+1]:
                isPalindrome[i][i+1] = True
        for l in range(3, n+1):
            for i in range(n):
                j = i + l - 1
                if j >= n:
                    break
                isPalindrome[i][j] = s[i] == s[j] and isPalindrome[i+1][j-1]
                
        min_cut = [float("inf")] * n + [0]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if isPalindrome[i][j]:
                    candidate_cut = 0 if j + 1 == n else min_cut[j+1] + 1
                    min_cut[i] = min(min_cut[i], candidate_cut)
        return min_cut[0]
    // dfs TLE 
    def helper(self, s, isPalindrome, start, cur_cut, min_cut) -> int:
        if cur_cut >= min_cut:
            return min_cut
        
        n = len(s)
        if start == n:
            return cur_cut
        
        for i in range(start, n):
            if isPalindrome[start][i]:
                new_cut = cur_cut + 1 if i != n - 1 else cur_cut
                min_cut = min(min_cut, self.helper(s, isPalindrome, i+1, new_cut, min_cut))
                              
        return min_cut
⚠️ **GitHub.com Fallback** ⚠️