131.分割回文串

题目描述

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

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

示例：
输入

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

思路

1. 使用回溯算法求解。

2.画出递归树（图片来自https://leetcode-cn.com/u/liweiwei1419/）。

3.根据递归树进行剪枝和递归操作即可。

Java代码实现

    public List<List<String>> partition(String s) {
        if(s.length() == 0)
            return new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        partition(s,0,s.length()-1,res,cur);
        return res;
    }

    private void partition(String s,int left,int right,List<List<String>> res,List<String> cur){
        if(left > right){
            res.add(new ArrayList<>(cur));
            return ;
        }
        for(int i=left;i<=right;i++){
            if(!judgePalindrome(s,left,i))
                continue;
            cur.add(s.substring(left,i+1));
            partition(s,i+1,right,res,cur);
            cur.remove(cur.size()-1);
        }
    }


    private boolean judgePalindrome(String s,int left,int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }