131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 public class Solution {
 2     private char[] s = null;
 3
 4     // 返回i位置开始k(k>j)位置结束的回文串的结束位置k
 5     private int nextLoc(int i, int j) {
 6         int l = -1, m, n;
 7         for (l = j+1; l < s.length; l++) {
 8             for (m = i, n = l; m < n; m++, n--) {
 9                 if (s[m] != s[n])
10                     break;
11             }
12             if (m >= n)
13                 return l;
14         }
15         return (l == s.length) ? -1 : l;
16     }
17
18     private void helper(int cur,List<String> subset, List<List<String>> res){
19         if (cur == s.length) {
20             res.add(new ArrayList<>(subset));
21             return;
22         }
23
24         for (int i = cur, j = cur; j != -1; ) {
25             subset.add(String.valueOf(s, i, j-i+1));
26             helper(j+1,subset, res);
27             subset.remove(subset.size()-1);
28             j = nextLoc(i,j);
29         }
30     }
31
32     public List<List<String>> partition(String s) {
33         this.s = s.toCharArray();
34         List<String> subset = new ArrayList<>();
35         List<List<String>> res = new ArrayList<>();
36         helper(0,subset, res);
37         return res;
38     }
39
40     public static void main(String[] args) {
41         Solution solution = new Solution();
42         List<List<String>> abaaab = solution.partition("abaaab");
43         for (List<String> e : abaaab) {
44             System.out.println(e);
45         }
46     }
47 }