当前位置：首页 > news >正文

分割回文串-leetcode

news 2026/5/23 11:21:57

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解法一

思路：

动态规划 (Dynamic Programming)：预处理回文状态

在回溯过程中，我们需要频繁判断子串 s[i...j] 是否为回文。如果每次都用双指针去判断，会产生大量重复计算。采用动态规划算法进行回文串的判断。

定义状态：f[i][j] 表示字符串从索引 i 到 j 的子串是否为回文。
转移方程：
- 如果 s[i] == s[j] 且它们中间的部分 s[i+1...j-1] 也是回文，那么 s[i...j] 就是回文。
- 即：f[i][j] = (s[i] == s[j]) && f[i+1][j-1]。
填表顺序：
- 注意外层循环是 i 从 n-1 到 0（逆序），内层循环是 j 从 i+1 到 n-1（正序）。
- 原因：计算 f[i][j] 时需要用到 f[i+1][j-1]。在二维矩阵中，f[i+1][j-1] 位于 f[i][j] 的“左下方”。通过逆序遍历 i，我们可以确保在计算当前行时，它下面的行已经计算好了。

有了 f[i][j] 状态表后，我们就可以通过 DFS（深度优先搜索）来寻找所有分割方案。

核心逻辑：
1. 做选择：从当前位置 i 开始，尝试所有可能的切点 j。如果 s[i...j] 是回文（通过 f[i][j] 直接获取），就把它放入当前路径 ans 中。
2. 递归：由于 s[i...j] 已经处理完，接下来的任务是从 j + 1 位置继续往后切。
3. 撤销选择（回溯）：当递归返回时，我们需要把刚才加入 ans 的子串弹出来，以便 for 循环继续尝试下一个可能的切点 j+1。
递归终点：当指针 i 到达字符串末尾 n 时，说明找到了一组完整的分割方案。

代码：

class Solution {boolean[][] f;List<List<String>> ret = new ArrayList<List<String>>();List<String> ans = new ArrayList<String>();int n;public List<List<String>> partition(String s) {n = s.length();f = new boolean[n][n];for (int i = 0; i < n; ++i) {Arrays.fill(f[i], 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];}}dfs(s, 0);return ret;}public void dfs(String s, int i) {if (i == n) {ret.add(new ArrayList<String>(ans));return;}for (int j = i; j < n; ++j) {if (f[i][j]) {ans.add(s.substring(i, j + 1));dfs(s, j + 1);ans.remove(ans.size() - 1);}}}
}

代码执行过程：

1.第一阶段：动态规划（填表）

代码首先通过 DP 计算所有子串是否为回文，得到一个布尔矩阵 f。 n = 3，矩阵大小为 3imes33imes3。

初始化：所有 f[i][j] 默认为 true。
核心计算（从下往上，从左往右）：
- 当 i=2：子串只有 "b"，f[2][2] 已经是 true。
- 当 i=1：
  - j=2：子串 "ab"。s[1]('a') != s[2]('b') →→ f[1][2] = false。
- 当 i=0：
  - j=1：子串 "aa"。s[0]('a') == s[1]('a') 且 f[1][0] 为 true →→ f[0][1] = true。
  - j=2：子串 "aab"。s[0]('a') != s[2]('b') →→ f[0][2] = false。

最终 f 矩阵（只看 j >= i 的部分）：

i \ j	0 (a)	1 (a)	2 (b)
0 (a)	T ("a")	T ("aa")	F ("aab")
1 (a)	-	T ("a")	F ("ab")
2 (b)	-	-	T ("b")

2.第二阶段：回溯（搜索方案）

我们从 dfs(s, 0) 开始，目标是把字符串切开。

1. 第一条路径：尝试从索引 0 切分

j = 0: f[0][0] 是 true (子串 "a")。
- 将 "a" 加入 ans。此时 ans = ["a"]。
- 递归执行 dfs(s, 1)：
  - j = 1: f[1][1] 是 true (子串 "a")。
    - 将 "a" 加入 ans。此时 ans = ["a", "a"]。
    - 递归执行 dfs(s, 2)：
      - j = 2: f[2][2] 是 true (子串 "b")。
        
        将 "b" 加入 ans。此时 ans = ["a", "a", "b"]。
        
        递归执行 dfs(s, 3)：i == n，找到第一个结果，存入 ret。
      - 回溯：从 ans 移除 "b"。
  - j = 2: f[1][2] 是 false ("ab" 不是回文)，跳过。
  - 回溯：从 ans 移除第二个 "a"。

2. 第二条路径：尝试另一种切法

j = 1: f[0][1] 是 true (子串 "aa")。
- 将 "aa" 加入 ans。此时 ans = ["aa"]。
- 递归执行 dfs(s, 2)：
  - j = 2: f[2][2] 是 true (子串 "b")。
    - 将 "b" 加入 ans。此时 ans = ["aa", "b"]。
    - 递归执行 dfs(s, 3)：i == n，找到第二个结果，存入 ret。
  - 回溯：从 ans 移除 "b"。
- 回溯：从 ans 移除 "aa"。