Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

Have you met this question in a real interview? 

Yes

Example

given s = "aab",
Return

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

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> result = new ArrayList<List<String>>();
        _partition(s, 0, result, new ArrayList<String>());
        return result;
    }
    
    private void _partition(String s, int start, List<List<String>> result, List<String> subList){
        
        if(start == s.length()){
            result.add(new ArrayList<String>(subList));
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isPalindrome(s.substring(start, i+1))){
                subList.add(s.substring(start, i+1));
                _partition(s, i+1, result, subList);
                subList.remove(subList.size()-1);
            }
        }
    }
    
    private boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(i < j){
            if(s.charAt(i) != s.charAt(j)) return false;
            i++; j--;
        }
        return true;
    }
}

DYNAMIC: