Given a strings, partition_s_such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

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>> ans = new ArrayList<>();
        List<String> sub = new ArrayList<>();
        if (s == null || s.length() == 0){
            return ans;
        }
        dfs(s, 0, sub, ans);
        return ans;
    }
    public void dfs(String s, int startIndex,
                    List<String> sub,List<List<String>> ans)
    {
        if (startIndex == s.length()) {
            ans.add(new ArrayList<String>(sub));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String part = s.substring(startIndex, i + 1);
            if (!isPalindrome(part)) {
                continue;
            }
            sub.add(part);
            dfs(s, i+1, sub, ans);
            sub.remove(sub.size() - 1);
        }
    }
    public boolean isPalindrome(String s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < s.length() && r >= 0 && l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}