131. Palindrome Partitioning ----M

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

A:

 Solution 1: brute-force solution,~~~~~ this is really stupid. 

(though we can add some dynamic programming philosophy on it.)

 第一思路，就是暴力破解。但是，太SB。

build a matrix, bool[][]  m = new bool[s.length(),s.length());

利用这个，类似于动态规划的方式，来build bottom up.

第三步，就是，利用10块糖的那道题，把每个字母，一个个加到尾巴上去。

首先，单独分开，加上的，肯定是可以的。

然后，就把刚加上的char ，和前面的依次combine起来s.substring(i,j+1)，如果是回环，则开始加入之前的。（并最后加入

to be more efficient, 用一个一位数组numPartitionAfterPosI[i] 定义了，刚刚加入s中位置为i的这个数字的时候，

有多少个partition.  并且，其对应的partition，都放在   返回变量的的arraylist<arraylist>的最前面。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i < n; i++) {
                int j = i + len - 1;
                if (j < n && s[i] == s[j] &&
                    (i + 1 >= j - 1 || isPal[i + 1][j - 1])) {
                    isPal[i][j] = true;
                }
            }
        }
        unordered_map < int, vector<vector<string>>> M; // length to partitioning
        M[0] = {{}};
        for (int end = 0; end < n; end++) {
            char ch = s[end]; // if s[end] map with 
            for(int start = end; start >=0 ; start--){
                if(isPal[start][end]){
                    for(auto pal : M[start]){// use start as the length of former length
                        pal.push_back(s.substr(start, end-start+1));
                        M[end+1].push_back(pal);
                    }
                }
            }
        }
        return M[n];
    }
}
;

Mistakes:

M[0] = {{}};   就可以了， 一开始写成了M[0] = {{“”}};

--------------------------------------非DP，  递归调用----------------------
 
思路很简单， 就是，每次取下前面的一个palindrome ，然后对剩下的string， 调用本函数。

public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
        // use recursive calling
        if (s.length() == 0) {
            return null;
        }
        ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
        if (s.length() == 1) {
            ArrayList<String> al = new ArrayList<String>();
            al.add(s);
            all.add(al);
            return all;
        }
    for (int i = 1; i <= s.length(); i++) {
            String preStr = s.substring(0, i);
            if (isPalin(preStr)) {
                ArrayList<ArrayList<String>> nextAll = partition(s.substring(i));
                if (nextAll == null) {
                    ArrayList<String> al = new ArrayList<String>();
                    al.add(preStr);
                    all.add(al);
                } else {
                    // iterate nextAll, and add preStr at the beginning
                    for (int j = 0; j < nextAll.size(); j++) {
                        nextAll.get(j).add(0, preStr);
                    }
                    all.addAll(nextAll);
                }
            }
        }
        return all;
    }

    boolean isPalin(String ss) {
        int i = 0, j = ss.length() - 1;
        while (i < j) {
            if (ss.charAt(i) != ss.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

}

Mistakes:
1: 哎，题目一上来，就理解错了。
 是partition s， for String s，就有pow(2, s.length())种不同的partition方式 （以后，面试的时候， 最少仔细看两遍题目，还是要再三问明白，然后，举个例子问面试官，看是否理解正确。）


 6: 我们一个个地加入， 当加入第j个char字符的时候， j字符，要和它前面的combine到一起。 当只和j-1 链接到一起的时候。 也要看j-2的palindrome的分割。
  // use j-2 instead of j -1, because j-1 is already combined with j  for(int i = j-1; i>=0; i--){ 这个的原因，就是头脑不清楚，没想明白，就开始写所导致。

7： 在这里

 for( int tt=0; tt< curList.size();tt++){
                                 // tt is the number of partitions that still in range[0,i-1]
                                 if(curLength > i){
                                     break;
                                 }

写成了 tt< listPartitionBeforeI.size()---------> 还是写的时候，头脑不清晰


--------------------------------------第二遍的时候，犯得错误，----------------------
1：   前面取preString 的时候，因为考虑，string.length() == 0的时候不好加
就i < s.length()了，可是，我们的设定是i 是ending position