Leetcode131. 分割回文串

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

题解：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 

代码如下：

class Solution {
    public List> partition(String s) {
        List> res = new ArrayList<>();
        if(s.length() == 0) {
            return res;
        }
        List path = new ArrayList<>();
        char[] charArray = s.toCharArray();
        dfs(charArray,0,path,res);
        return res;
    }
    private void dfs(char[] charArray, int begin, List path, List> res) {
        if(begin == charArray.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin; i < charArray.length;i++){
            if(!checkPalindrome(charArray, begin, i)){
                continue;
            }
            path.add(new String(charArray, begin, i - begin + 1));
            dfs(charArray, i+1,path,res);
            path.remove(path.size()-1);
        }
    }
    private boolean checkPalindrome(char[] charArray,int left, int right) {
        
        while(left < right) {
            if(charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
        
    }
}