大家好！我是曾续缘❣️
今天是《LeetCode 热题 100》系列
发车第 61 天
回溯第 7 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个字符串 s，请你将s分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
难度：💖💖

解题方法

问题的目标是以分割的方式处理字符串，使得每个子串都是回文串。

首先，我们需要判断一个子串是否是回文串。为了快速判断，我们使用动态规划。

知道了字符串可以在哪里分割，我们需要不重不漏地枚举分割方案，使得每种分割方案都处理完字符串。我们使用回溯法不断尝试。

动态规划部分

定义状态： f[i][j] 表示字符串 s 的子串 s[i...j] 是否是回文串。
初始化状态： 所有 f[i][j] 初始化为 true，因为单个字符都是回文串，同时需要保证[i+1][i]为true，方便后续处理，可以理解为空串也是回文串。
状态转移方程： 如果 s[i] == s[j]，那么 f[i][j] 取决于 f[i+1][j-1]（即去掉 s[i] 和 s[j] 的子串是否为回文串）。
状态转移方向：因为i取决于i+1，因此倒序枚举i，因为j取决于j-1，因此顺序枚举j。

回溯法部分

递归函数： backtrack(f, s, i) 是一个递归函数，用于从字符串 s 的第 i 个字符开始尝试所有可能的回文子串。
递归终止条件： 当 i 到达字符串的长度时，说明已经考虑了整个字符串，此时将当前的 tmp 列表添加到 ans 列表中。
递归步骤： 对于每个可能的 j > i，如果 f[i][j] 为 true，说明 s[i...j] 是一个回文串。于是我们可以将 s.substring(i, j + 1) 添加到 tmp 列表中，并递归地调用 backtrack 函数考虑剩下的字符串。在递归调用返回后，我们需要将刚才添加的元素从 tmp 中移除，这样可以回溯到之前的状态。

Code

查看代码

java

class Solution {
    List<List<String>> ans;
    List<String> tmp;

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

    private void backtrack(boolean[][] f, String s, int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<String>(tmp));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (f[i][j]) {
                tmp.add(s.substring(i, j + 1));
                backtrack(f, s, j + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

解题方法 ​

动态规划部分 ​

回溯法部分 ​

Code ​

解题方法

动态规划部分

回溯法部分

Code