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();
        if(n==0)
            return vector<vector<string>>();
        vector<vector<bool>> A;
        for(int i =0;i<n;++i)  // 
            A.push_back(vector<bool>(n,false));
        // setup the flag that whether (i,j) is palindrome
        for(int len = 1;len<=n; ++len)
            for(int start=0;start+len-1<n;++start)
            {
                int end = start+len-1;
                A[start][end] = s[start] == s[end] && (start+1<=end-1? A[start+1][end-1] :true );
            }
        
        vector<vector<vector<string>>> ALL; // ALL[i] is all palindrome ending at index i
        for(int end =0; end<n; ++end) // newly added character s[end]
        {
            vector<vector<string>> newRes;
            for(int start=end;start>=0; --start)
            {
                if( not A[start][end])
                    continue;
                string newPalin = s.substr(start,end+1-start);
                if(start == 0)
                {
                    newRes.push_back(vector<string>{newPalin});
                }else{
                    for(vector<string>& V : ALL[start-1]) //use start, not start-1, as ALL[0] is ""
                    {
                        vector<string> tmp(V);
                        tmp.push_back(newPalin);
                        newRes.push_back(tmp);
                    }
                }    
            }
            ALL.push_back(newRes);
        }
        return ALL[n-1];
    }
};

Mistakes:

            ALL.push_back(newRes);

提上了一个}里，TMMD，随手写的。  真日

--------------------------------------非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