分割回文字符串 | LeetCode-131 | 回溯算法

回溯算法练习题

---

LeetCode链接：131. 分割回文串

---

题目1：131. 分割回文串

1.题目描述

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

示例 1：

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

示例 2：

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

提示：

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

2.题解

2.1 回溯

class Solution {
    // 保存所有符合条件的回文分割方案
    List<List<String>> result = new ArrayList<>();
    // 当前回溯路径，用于保存一次递归过程中生成的回文子串
    List<String> path = new ArrayList<>();

    // 主函数，接收字符串并启动回溯过程
    public List<List<String>> partition(String s) {
        // 从字符串的第 0 个字符开始进行回溯
        backtracking(s, 0);
        // 返回最终的所有回文分割方案
        return result;
    }

    // 回溯函数，递归生成回文子串的组合
    public void backtracking(String s, int start) {
        // 当 start 达到字符串末尾时，说明已经找到了一个完整的分割方案
        if (start == s.length()) {
            // 将当前路径（回文组合）添加到结果列表中
            result.add(new ArrayList<>(path));
            return;
        }

        // 从 start 开始，尝试截取不同长度的子串
        for (int i = start; i < s.length(); i++) {
            // 获取从 start 到 i 的子串
            String sub = s.substring(start, i + 1);
            // 如果子串是回文，则将其加入路径并继续递归
            if (isPalindrome(sub)) {
                // 添加当前回文子串到路径中
                path.add(sub);
                // 递归处理从 i+1 开始的剩余字符串
                backtracking(s, i + 1);
                // 回溯，撤销上一步的选择，将最后一个子串移除
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断字符串是否为回文
    public boolean isPalindrome(String s) {
        // 双指针法，左指针从头，右指针从尾部向中间移动
        int left = 0, right = s.length() - 1;
        // 比较字符串左右两端的字符，直到左指针超过右指针
        while (left < right) {
            // 如果左右字符不相等，则不是回文
            if (s.charAt(left) != s.charAt(right)) return false;
            // 移动左右指针
            left++;
            right--;
        }
        // 如果没有发现不相等的字符，则是回文
        return true;
    }
}

题目2：132. 分割回文串 II

1.题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

2.题解

2.1 写法1-超时

class Solution {
    int min = Integer.MAX_VALUE;
    List<String> path = new ArrayList<>();

    public int minCut(String s) {
        backtracking(s,0);
        return min;
    }

    public void backtracking(String s, int start) {
        if (start == s.length()) {
            min = path.size()-1 < min ? path.size()-1 : min;
            return;
        }

        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (isPalindrome(sub)) {
                path.add(sub);
                backtracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

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