分割回文串

131. 分割回文串

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

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

用下标left和right来控制子字符串的遍历

如果[left,right)是回文串，继续递归[right,right+1];

如果[left,right)不是回文串，遍历[left,right+1)

代码

class Solution {

    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        traversal(s,0);
        return ans;
    }

    public void traversal(String s, int left){
        if(left == s.length()){ //左下标遍历完字符串，结束递归
            ans.add(new ArrayList<>(path));
            return;
        }
        //用i遍历子字符串的右下标
        for(int i = left; i < s.length(); i++){
            String str = s.substring(left, i+1);
            if(!isPalindromicStr(str)){//如果子字符串不是回文，直接跳过
                continue;
            }
            path.add(str);
            traversal(s, i);
            path.remove(path.size()-1);
        }
    }

    //判断是否为回文串
    public boolean isPalindromicStr(String s){
        int len = s.length();
        for(int i = 0; i < len/2; i++){
            if(s.charAt(i)== s.charAt(len-1-i)){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
}