131. Palindrome Partitioning.md

public class Solution {
    List<List<String>> resultLst;
	    ArrayList<String> currLst;
    public List<List<String>> partition(String s) {
        resultLst = new ArrayList<List<String>>();
	    currLst = new ArrayList<String>();
        if(s.length()<1) return resultLst;  //0
        if(s.length()==1) {       //case 1
            currLst.add(s);
            resultLst.add(currLst);
            return resultLst;
        }
        
        //general way
        backTrack(s,0);
	    return resultLst;
    }
    public void backTrack(String s, int l) {
        if(currLst.size()>0 && l>=s.length()) {//the initial str could be palindrome
	        List<String> r = (ArrayList<String>) currLst.clone();
	        resultLst.add(r);
        }
        for(int i = l; i < s.length(); i++) {
            if(isPalindrome(s,  l,  i)) {
                if(l==i) {   //single char
                    currLst.add(Character.toString(s.charAt(i)));
                }
                else currLst.add(s.substring(l,i+1));
                
                backTrack(s, i+1);
                currLst.remove(currLst.size()-1); //remove for the botttom
            }
        }
    }
    
    public boolean isPalindrome(String str, int l, int r) {
        if(l==r) return true;
        while(l<r) {
            if(str.charAt(l)!=str.charAt(r)) return false;
            l++;r--;
        }
        return true;
    }
}



//List<List<String>> list = new ArrayList<List<String>>(); correct
//List<List<String>> list = new ArrayList<ArrayList<String>>(); wrong

/* the type to judge the palindrome
public boolean isPalindrome(String str, int l, int r) {
        if(l==r) return true;
        while(l<r) {
            if(str.charAt(l)!=str.charAt(r)) return false;
            l++;r--;
        }
        return true;
    }
*/