131. 分割回文串

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

回溯把字符串切割成多个子串，如果当前切割字串为回文串则进行下一轮切割，否则继续延长子串直到找到回文串为止。

解法

下一轮递归位置为上一轮截取位置的下一位。

class Solution {

    List<List<String>> result = new ArrayList<>();

    List<String> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return result;
        }
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(list));
            return;
        }
        int len = 0;
        while (start + len < s.length()) {
            //如果是回文串，则进行下一轮切割
            if (isPalindrome(s, start, start + len)) {
                list.add(s.substring(start, start + len + 1));
                //下一次开始位置为当前结束位置+1
                backtracking(s, start + len + 1);
                list.remove(list.size() - 1);
            }
            len++;
        }
    }

    /**
     * 判断回文串
     */
    public boolean isPalindrome(String s, int start, int end) {
        while (start <= end && s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
        }
        return (start == end + 1) || (start == end + 2);
    }
}