Question:

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

Thinking:

We should get all the possible partition, it’s obvious we should use backtracing. We partition the string from beginning, and check if it’s palindrome, then check the rest of the substring. If all the substrings are palindrome, we put them in the result. We have to notice the API of Java substring(beginIndex, endIndex) that beginIndex is inclusive but endIndex is exclusive.

Solution:

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<List<String>>();
    int len = s.length();
    if (palindrome(s)){
        List<String> tempres = new ArrayList<String>();
        tempres.add(s);
        res.add(tempres);
    }
    for (int i = 1; i < len; i++){
        if (palindrome(s.substring(0, i))){
            for (List<String> list: partition(s.substring(i))){
                list.add(0, s.substring(0, i));
                res.add(list);
            }
        }
    }
    return res;
}

private boolean palindrome(String s){
    int len = s.length();
    int left = 0;
    int right = len - 1;
    while (left < right){
        if (s.charAt(left) != s.charAt(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}