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

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>();
        dfs(s,0);
        return resultLst;
        }

    // DFS
    public void dfs(String s, int l){
        if (currLst.size()>0 && l>=s.length()){
            List<String> r = (ArrayList<String>) currLst.clone();
            resultLst.add(r);
        }
        for (int i=l;i<s.length();i++){
            if(isPalindrome(s,l,i)){
                currLst.add(s.substring(l,i+1));
                dfs(s,i+1);
                currLst.remove(currLst.size()-1);
            }
        }
    }

    public boolean isPalindrome(String s, int i, int j){
        if (i > j) return false;
        while (i<j){
            if (s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

class Solution(object):
    def isParlindrome(self,s):
        start = 0
        end = len(s) - 1
        while start<end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

    # DFS
    def partition_dfs(self, result, vector, s, start,end):
        if start >= end:
            result.append(vector)
            return

        for i in range(start,end):
            new_str = s[start:i+1]
            if self.isParlindrome(new_str):
                self.partition_dfs(result,vector+[new_str],s,i+1,end)
        return

    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        result = []
        if s == None:
            return result
        self.partition_dfs(result,[],s,0,len(s))
        return result