LeetCode Hot100 131.分割回文串

题目：

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

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

方法：灵神-子集型回溯

假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。

也可以理解成：是否要把?s[i]s[i]s[i]?当成分割出的子串的最后一个字符。

代码：

class Solution {
    private final List<List<String>> ans = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0, 0);
        return ans;
    }

    private boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--))
                return false;
        }
        return true;
    }
    // start 表示当前这段回文子串的开始位置
    private void dfs(int i, int start) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        
        // 不选 i 和 i + 1 之间的逗号（i = n - 1 时一定要选）
        if (i < s.length() - 1)
            dfs(i + 1, start);
        
        // 选 i 和 i + 1 之间的逗号（把 s[i] 作为子串的最后一个字符）
        if (isPalindrome(start, i)) {
            path.add(s.substring(start, i + 1));
            dfs(i + 1, i + 1);              // 下一个子串从 i+1 开始
            path.remove(path.size() - 1);   // 恢复现场
        }
    }
}