给定一个字符串 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 }