[LeetCode] 每日一题 131. 分割回文串

题目链接

https://leetcode.cn/problems/palindrome-partitioning

题目描述

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

回文 串是向前和向后读都相同的字符串。

示例输入

示例 1

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

示例 2

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

提示

• 1 <= s.length <= 16

• s 仅由小写英文字母组成

解题思路

本题的目标是将字符串 s 分割成多个回文子串，返回所有可能的分割方案。为了高效地求解，我采用了回溯和动态规划的结合。首先，使用动态规划（DP）来判断给定字符串的各个子串是否是回文串。具体做法是，通过递推公式，判断字符串的首尾字符是否相同，且中间部分是否为回文串，从而判断整个子串是否为回文串。然后，利用回溯算法来枚举所有可能的分割方案

代码实现

class Solution {
    boolean[][] dp;
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        int n = s.length();
        dp = new boolean[n][n];
        for (boolean[] arr : dp) {
            Arrays.fill(arr, true);
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
            }
        }
        backtrace(s, 0);
        return ans;
    }

    private void backtrace(String s, int index) {
        if (index == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (dp[index][i]) {
                path.add(s.substring(index, i + 1));
                backtrace(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
}

复杂度分析

时间复杂度：总体时间复杂度为 O(n^2)

• 动态规划部分：构建 dp 数组需要遍历所有的子串，时间复杂度是 O(n^2)，其中 n 是字符串 s 的长度

• 回溯部分：每次回溯都会遍历从当前索引到字符串末尾的所有位置，而每个子串的判断都是 O(1)，因此回溯的时间复杂度也是 O(n^2)

空间复杂度：总的空间复杂度为 O(n^2)

• dp 数组的空间复杂度是 O(n^2)，用于存储每个子串是否是回文串的信息

• 回溯栈的空间复杂度是 O(n)，因为最多需要递归 n 层

总结

本题通过回溯和动态规划的结合高效解决了分割回文串的问题。动态规划帮助我们预处理所有子串是否是回文串，减少了回溯时的计算量，而回溯则确保了能够枚举出所有的分割方案。这种方法在时间和空间上都是优化过的，能够高效地解决该问题

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。