// @Title: 分割回文串 (Palindrome Partitioning)
// @Author: qisiii
// @Date: 2024-09-19 23:36:27
// @Runtime: 8 ms
// @Memory: 56.2 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), s, 0);
        return result;
    }
    //切割和组合的逻辑其实差不多，组合是选了一个时候从剩下的里面选，切割是切了一刀后，从剩下的里面切
    private void dfs(List<List<String>> result, List<String> splitList, String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList(splitList));
            return;
        }
        // 从start开始切,切到i为止
        //边界的判断很重要，决定了跳出条件，判断回文逻辑和切割逻辑，这里我选的是[start,i]
        for (int i = start; i < s.length(); i++) {
            if (!isPalindrome(s, start, i)) {
                continue;
            }
            splitList.add(s.substring(start, i+1));
            dfs(result, splitList, s, i+1);
            splitList.remove(splitList.size() - 1);
        }
    }

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