​131. Palindrome Partitioning

131. 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.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

My Solutions:

对每一个index和后面的index组成的substring进行backtrack，如果位置（start）走到最后，把临时的arraylist加入结果res。

Time: O(n*2^n)，对于每个位置，可以选择切或者不切割；判断isPal需要n次

public class Solution {

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        helper(res, s, new ArrayList<>(), 0);
        return res;
    }
    private void helper(List<List<String>> res, String s, List<String> curr, int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(curr));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (isPal(sub)) {
                curr.add(sub);
                helper(res, s, curr, i);
                curr.remove(curr.size() - 1);
            }
        }
    }
    private boolean isPal(String str) {
        int l = 0, r = str.length() - 1;
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }

}