Leetcode:132. split palindrome string II

Title source

• leetcode：132. Split palindrome string II

Title Description

class Solution {
    
public:
    int minCut(string s) {
    

    }
};

title

Analyze the amount of data

• $10^3$, So the algorithm has the highest time complexity $O(N^2)$, It can be used dp To do it

Analyze the meaning of the question

Try the model from left to right

Ideas

class Solution {
    
    bool ispalindrome(std::string str, int i, int j){
    
        if(i == j){
    
            return true;
        }
        while ( i < j){
    
            if(str[i] != str[j]){
    
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    //  from str[begin....] At least a few palindromes can be formed at the beginning 
    int process(std::string &str, int begin){
    
        int N = str.size();
        if(begin == N){
    
            return 0;
        }

        if(begin == N - 1){
    
            return 1;
        }

        int next = INT32_MAX;
        for (int end = begin; end < str.size(); ++end) {
    
            if(ispalindrome(str, begin, end)){
    
                next = std::min(next, 1 +  process(str, end + 1));
            }
        }
        return next;
    }

public:
    int minCut(string s) {
    
        if(s.size() < 2){
    
            return 0;
        }
        
        return process(s, 0) - 1;
    }
};

Will timeout （ Time complexity O(N^3)）.

class Solution {
    
    bool ispalindrome(std::string str, int i, int j){
    
        if(i == j){
    
            return true;
        }
        while ( i < j){
    
            if(str[i] != str[j]){
    
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
public:
    int minCut(string str) {
    
        if(str.size() < 2){
    
            return 0;
        }
        int N = str.size();
        std::vector<int> dp(N + 1);
        dp[N] = 0;
        dp[N - 1] = 1;
 
        for (int begin = N - 2; begin >= 0; --begin) {
    
            int next = INT32_MAX;
            for (int end = begin; end < N; ++end) {
    
                if(ispalindrome(str, begin, end)){
    
                    next = std::min(next, 1 + dp[end + 1]);
                }
            }
            dp[begin] = next;
        }
        return dp[0] - 1;
    }
};

Or overtime

Pretreatment structure ： Definition dp[i][j] From [i…j] Is it a palindrome

（0）dp The length is N - 1, The height is N - 1
（1） When $i<j$ when , Cannot form effective interval , So useless
（2） initialization dp surface

• First step ： Fill diagonal ,dp[i][i] = true
• The second step ： Fill in the penultimate diagonal （j = i + 1）： When str[i] == str[i + 1] when ,dp[i][j + 1] = true
  

（3） about dp[i][j] How to fill in the general situation

• If str[i] ！= dp[j], fill false
• otherwise ,dp[i][j] = dp[i + 1][j - 1]

class Solution {
    
    std::vector<std::vector<bool>>  checkPalindrome(string str){
    
        int N = str.size();
        std::vector<std::vector<bool>> dp(N, std::vector<bool>(N));
        for (int i = 0; i <= N - 1; ++i) {
    
            dp[i][i] = true;
        }
        for (int i = 0; i <= N - 2; ++i) {
    
            dp[i][i + 1] = str[i] == str[i + 1];
        }

        for (int i = N - 2; i >= 0; --i) {
    
            for (int j = i + 2; j <= N - 1; ++j) {
    
                dp[i][j] = str[i] == str[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }
public:
    int minCut(string str) {
    
        if(str.size() < 2){
    
            return 0;
        }
        int N = str.size();
        std::vector<int> dp(N + 1);
        dp[N] = 0;
        dp[N - 1] = 1;

        auto check = checkPalindrome(str);
        
        for (int begin = N - 2; begin >= 0; --begin) {
    
            int next = INT32_MAX;
            for (int end = begin; end < N; ++end) {
    
                if(check[begin][end]){
    
                    next = std::min(next, 1 + dp[end + 1]);
                }
            }
            dp[begin] = next;
        }
        return dp[0] - 1;
    }
};

Expand

Returns a possible segmentation

Examples to be added

Realization

class Solution {
    
    std::vector<std::vector<bool>>  checkPalindrome(string str){
    
        int N = str.size();
        std::vector<std::vector<bool>> dp(N, std::vector<bool>(N));
        for (int i = 0; i <= N - 1; ++i) {
    
            dp[i][i] = true;
        }
        for (int i = 0; i <= N - 2; ++i) {
    
            dp[i][i + 1] = str[i] == str[i + 1];
        }

        for (int i = N - 2; i >= 0; --i) {
    
            for (int j = i + 2; j <= N - 1; ++j) {
    
                dp[i][j] = str[i] == str[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }
public:
    std::vector<std::string> minCut(string str) {
    
        int N = str.size();
        std::vector<int> dp(N + 1);
        dp[N] = 0;
        dp[N - 1] = 1;

        auto check = checkPalindrome(str);

        for (int begin = N - 2; begin >= 0; --begin) {
    
            int next = INT32_MAX;
            for (int end = begin; end < N; ++end) {
    
                if(check[begin][end]){
    
                    next = std::min(next, 1 + dp[end + 1]);
                }
            }
            dp[begin] = next;
        }



        std::vector<std::string> ans;
        for (int i = 0, j = 1; j <=  N; ++j) {
    
            if(check[i][j - 1] && dp[i] == dp[j] + 1){
    
                ans.emplace_back(str.substr(i, j - i));
                i = j;
            }
        }

        return ans;
    }
};

Returns all possible results （ To be completed ）