分割回文串

问题陈述

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

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

示例:

1
2
3
4
5
6
7
8
输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]


思路实现

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> partitions=new ArrayList<>();
        List<String> curpartion=new ArrayList<>();
        doPartition(s,partitions,curpartion);
        return partitions;

    }
    private void doPartition(String s,List<List<String>> partitions,List<String> curpartion){
        if(s.length()==0){
            partitions.add(new ArrayList<>(curpartion));
            return;
        }
        for(int i=0;i<s.length();i++){
            if(isPalindrome(s,0,i)){
                curpartion.add(s.substring(0,i+1));
                doPartition(s.substring(i+1),partitions,curpartion);
                curpartion.remove(curpartion.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s,int i,int j){
        while(i<j){
            if(s.charAt(i++)!=s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}