[LeetCode]Palindrome Partitioning

题目传送门

题目描述：给定一个字符串 s，要求将其切分成若干子串，使得每个子串都是回文串（即正着读和反着读相同），并返回所有可能的切分方案，每种方案是一个由子串组成的列表；最终结果是所有合法方案的集合。

代码：

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        partition(result, s, 0, new ArrayList<>());
        return result;
    }

    public void partition(List<List<String>> result, String s, int index, List<String> lastArray) {
        if (index >= s.length()) {
            result.add(new ArrayList<>(lastArray));
            return;
        }
        for (int i = index + 1; i <= s.length(); i++) {
            String substring = s.substring(index, i);
            if (validPalindrome(substring)) {
                lastArray.add(substring);
                partition(result, s, i, lastArray);
                lastArray.removeLast();
            }
        }
    }

    private boolean validPalindrome(String s) {
        for (int i = 0; i <= (s.length() - 1) / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

代码思路：这段代码的核心思路是回溯（DFS）+ 枚举切割点：从字符串起始位置开始，逐步尝试将字符串切分成不同长度的前缀子串，对于每一个子串先判断是否为回文，如果是就加入当前路径（lastArray），然后递归处理剩余部分；当遍历到字符串末尾时，说明当前路径是一种合法的回文划分方案，将其加入结果集中；递归返回时再撤销上一步选择（回溯），继续尝试其他切分方式，从而穷举出所有可能的回文分割组合。