Problem

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

Return all possible palindrome partitioning of s.

Example

Given s = "aab", return:

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

Note

backtracking, 指针溢出时添加新的结果到res集合。

Solution

public class Solution {
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> tem = new ArrayList<String>();
        if (s.length() == 0 || s == null){
            return res;
        }
        dfs(res, tem, s, 0);
        return res;
    }
    public void dfs(List<List<String>> res, List<String> tem, String s, int start){
        if (start == s.length()){
            res.add(new ArrayList<String>(tem));
            return;
        }
        for (int i = start; i < s.length(); i++){
            String str = s.substring(start, i + 1);
            if (isPalindrome(str)){
                tem.add(str);
                dfs(res, tem, s, i + 1); //start+=1
                tem.remove(tem.size() - 1);
            }
        }
    }
    public boolean isPalindrome(String str){
        int l = 0;
        int r = str.length()-1;
        while (l < r){
            if (str.charAt(l) != str.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}