131. 分割回文串

---

题目

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

示例： 示例 1:

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

示例 2:

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

---

解题思路

核心方法

回溯法 + 回文串判断：

1. 路径选择：维护一个临时列表 temp，存储当前已分割的回文子串。
2. 递归终止条件：当当前分割起点 depth 等于字符串长度时，将当前临时列表加入结果列表。
3. 回溯过程：
   • 从 depth 开始遍历字符串，截取子串 s[depth..i]。
   • 若该子串是回文串，将其加入临时列表，递归进入下一层（分割起点为 i+1）。
   • 递归返回后，将该子串从临时列表中移除，继续尝试其他分割方式。
4. 回文串判断：通过双指针法判断子串是否为回文串（左右指针向中间移动，比较字符是否相等）。

---

代码实现

回溯法（Java）

import java.util.*;

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    
    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return ans;
    }
    
    public void dfs(String s, int depth) {
        if (depth == s.length()) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = depth; i < s.length(); i++) {
            String curr = s.substring(depth, i + 1);
            if (isPalindrome(curr)) {
                temp.add(curr);
                dfs(s, i + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

---

复杂度分析

• 时间复杂度：O(n * 2^n)，其中 n 是字符串的长度。字符串有 2^(n-1) 种分割方式，每种分割方式需要 O(n) 的时间判断回文串并复制结果。
• 空间复杂度：O(n)，递归栈的深度为 n，临时列表的空间也为 n。

---

总结

1. 回溯法通过尝试所有可能的分割方式，结合回文串判断，能够高效生成所有有效的分割方案。
2. 双指针法判断回文串的时间复杂度为 O(n)，实现简洁高效。
3. 该方法适用于字符串长度较短的场景（题目限制 1 <= s.length <= 16），性能表现良好。

---