Leetcode 131: palindrome partition // Leetcode 132: palindrome partition II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ] 

这道题也是典型的dp，属于cut rope类似的问题，linear 回头scan 之前的解，进行拼接。

这一题时间复杂度O（N^2），先用一个dp把palindrome的问题解决，再利用第一个dp 里的答案，

用第二个dp解minimal cut . 

class Solution {
public:
    int minCut(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        //dp1: check if palindrome
        bool M[s.size()][s.size()];
        //base case
       for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if ((i == j) || (s[i] == s[j] && (i == j-1 || M[i+1][j-1]) ) ) M[i][j] = true;
                else M[i][j] = false;
            }
        }
        //dp2: find minimal cut
        int cut[s.size()];
        //base case
        cut[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            //case 1: string is palindrome
            if (M[0][i]) cut[i] = 0;
            else {
                int min_cut = s.size();
                for (int j = 0; j < i; j++) {
                    if (M[j+1][i]) {
                        min_cut = min(min_cut, cut[j]);
                    }
                }
                cut[i] = min_cut + 1;
            }
        }
        return cut[s.size()-1];
    }
}; 

updated:

双重DP, 可以把上面两个DP放到一个for for循环里面， 但是需要做一点修改，partition breaK的时候从后往前break。 这样就可以统一了。

class Solution {
public:
    int minCut(string s) {
        if (s.size() == 0) return 0;
        vector<int> buf(s.size(), false);
        vector<vector<int>> matrix(s.size(), buf);
        int M[s.size()+1]; // M[i] represent the minimal cuts of substr 0-i
        //base case
        for (int i = 0; i < s.size(); i++) {
            M[i] = s.size()-i;
        }
        M[s.size()] = 0;
        for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i; j < matrix[0].size(); j++) {
                if ((i == j) || (s[i] == s[j] && (j == i+1 || matrix[i+1][j-1]))) {
                    matrix[i][j] = true;
                    M[i] = min(M[i], M[j+1] +1);
                }
            }
        }
        return M[0]-1;
    }
};

Palindrome partition II

M1: dp + dfs:

大集合超时！！！！ 

class Solution {
private:
    void DFS(vector<vector<string>> &rst, vector<string> solu, string s, int position, vector<vector<bool>> M) {
        //base case
        if (position == s.size()) {
            rst.push_back(solu);
            return;
        }
        for (int i = 0; i + position < s.size(); i++) {
            if (M[position][position + i]) {
                solu.push_back(s.substr(position, i+1));
                DFS(rst, solu, s, position+i+1,M);
                solu.pop_back();
            }
        }
    } 
public:
//use dfs
    vector<vector<string>> partition(string s) {
        vector<string> solu;
        vector<vector<string>> rst;
        //sanity cehck
        if (s.size() == 0) return rst;
         //dp1: check if palindrome
         vector<bool> M1(s.size(), false);
         vector<vector<bool>> M(s.size(), M1);
        //base case
        for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if ((i == j) || (s[i] == s[j] && (i == j-1 || M[i+1][j-1]) ) ) M[i][j] = true;
                else M[i][j] = false;
            }
        }
        DFS(rst, solu, s, 0, M);
        return rst;
    }
}; 

updated: 

上面代码超时主要原因： 二维数组bool M用vector<vector<bool>> 来定义，并且利用一维vector

来对这个二维vector进行初始化，二维vector的操作处理时间极慢无比，为了传递给函数二维数组，

直接定义一个二维数组是不能进行传参数进函数的，除非有固定的列的数目，但是为了保险，以后

所有需要传递二维数组进函数参数的问题，都必须要二维指针操作， bool ** M， 并且同时用new

对这个二维指针进行初始化， 然后直接传入 bool**　Ｍ　进入函数就可以，　最后函数结束，需要

把新ｎｅｗ出来的二维指针删除。　 

bool **M = new bool*[s.size()];

for (int i = 0; i < s.size(); i++) {
    M[i] = new bool[s.size()];
    M[i][i] = true;
 }

３６ｍｓ　过大集合！！！

class Solution {
private:
    void DFS(vector<vector<string>> &rst, vector<string> solu, string s, int position, bool** M) {
        //base case
        if (position == s.size()) {
            rst.push_back(solu);
            return;
        }
        for (int i = 0; i + position < s.size(); i++) {
            if (M[position][position + i]) {
                solu.push_back(s.substr(position, i+1));
                DFS(rst, solu, s, position+i+1,M);
                solu.pop_back();
            }
        }
    } 
public:
//use dfs
    vector<vector<string>> partition(string s) {
        vector<string> solu;
        vector<vector<string>> rst;
        //sanity cehck
        if (s.size() == 0) return rst;
         //dp1: check if palindrome
         bool **M = new bool*[s.size()];
         for (int i = 0; i < s.size(); i++) {
             M[i] = new bool[s.size()];
             M[i][i] = true;
         }
        //base case
        for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i+1; j < s.size(); j++) {
                if (s[i] == s[j] && (i == j-1 || M[i+1][j-1])) M[i][j] = true;
                else M[i][j] = false;
            }
        }
        DFS(rst, solu, s, 0, M);
        for (int i = 0; i < s.size(); i++) {
            delete[] M[i];
        }
        delete[] M;
        return rst;
    }
};