Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

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

In the given example,
["a", "a", "b"] comes before ["aa", "b"] because len("a") < len("aa")

Method:

Keep dividing the string, add to string list if current substring is a palindrome, and recursively call the rest of the string.

Solution:

Time: O(n*n!)
Space: O(n*n!)

public class Solution {
    public ArrayList<ArrayList<String>> partition(String a) {
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        ArrayList<String> current = new ArrayList<>();
        helper(result, current, a);
        return result;
    }
    
    private void helper(ArrayList<ArrayList<String>> result, ArrayList<String> current, String a) {
        if (a == null || a.length() == 0) return;
        for (int i = 1; i < a.length(); i ++) {
            String sub = a.substring(0, i);
            if (isP(sub)) {
                current.add(sub);
                helper(result, current, a.substring(i, a.length()));
                current.remove(current.size() - 1);
            }
        }
        if (isP(a)) {
            current.add(a);
            result.add(new ArrayList<>(current));
            current.remove(current.size() - 1);
        }
    }
    
    private boolean isP(String a) {
        int left = 0;
        int right = a.length() - 1;
        while (left < right) {
            if (a.charAt(left) != a.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}