131. Palindrome Partitioning

Leetcode Backtracking

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"]
]

分析

比较规矩的回溯法的问题。注意细节即可。

private List<List<String>> res;
public List<List<String>> partition(String s) {
    res = new ArrayList<>();
    partitionHelper(new ArrayList<>(), s);
    return res;
}

private void partitionHelper(ArrayList<String> list, String s) {
    if (s.length() == 0) {res.add(list); return; }
    int i = 1, n = s.length();
    while (i <= n) {
        String sub = s.substring(0, i);
        if (!isValidPalindrome(sub)) {i++; continue;}
        list.add(sub);
        partitionHelper((ArrayList<String>) list.clone(), s.substring(i, n));
        list.remove(list.size() - 1);
        i++;
    }
}

private boolean isValidPalindrome(String s) {
    if (s == null) return false;
    int left = 0, right = s.length() - 1;
    while (left <= right)
        if (s.charAt(left++) != s.charAt(right--)) return false;

    return true;
}