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.

For example, given s = "aab",
Return

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

Java

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> sols = new ArrayList<List<String>>();
        helper(s, 0, new ArrayList<String>(), sols);
        return sols;
    }

    private void helper(String s, int start, List<String> sol, List<List<String>> sols) {
        if(start == s.length()) {
            sols.add(new ArrayList<String>(sol));
            return;
        }

        for(int i = 1; i <= s.length() - start; i++) {
            String str = s.substring(start, start + i);
            if(isValid(str)) {
                sol.add(str);
                helper(s, start + i, sol, sols);
                sol.remove(sol.size() - 1);
            } 
        }
    }

    private boolean isValid(String str) {
        int i = 0;
        int j = str.length() - 1;

        while(i <= j) {
            if(str.charAt(i) == str.charAt(j)) {
                i++;
                j--;
            } else {
                return false;
            }
        }
        return true;
    }
}