分割回文串

原题链接

使用的方法

回溯算法

解题思路

• 给定一个字符串 s，将 s 分割成一些子串，使得每个子串都是回文串。返回 s 所有可能的分割方案。
• 我们可以使用回溯算法来生成所有可能的分割方案。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过递归地构建分割方案来生成所有的组合。
• 我们从字符串的起始位置开始，逐步尝试将字符串分割成子串。在每一步，我们有一个选择：要么将当前子串添加到分割方案中，要么继续尝试更长的子串。我们需要确保在添加子串之前检查它是否是回文串，以保持分割方案的有效性。
• 递归的终止条件是当我们处理到字符串的末尾时，我们将当前的分割方案添加到结果列表中。通过这种方式，我们可以生成所有可能的分割方案，并最终返回结果列表。

代码实现

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

    public void backtrack(String s,int start){
        // 说明已到末尾
        if(start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        // 从 start 开始尝试
        for(int end = start; end < s.length(); end++){
            if(isPalindrome(s,start,end)){
                path.add(s.substring(start,end+1));
                backtrack(s,end+1);
                path.remove(path.size() - 1);
            }
        }
    }
    public boolean isPalindrome(String s,int left ,int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}