LeetCode 131 分割回文串

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

示例 1：

输入：s = "aab"

输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"

输出：[["a"]]

提示：

1 <= s.length <= 16

s 仅由小写英文字母组成

Python代码：

from typing import Listclass Solution:def partition(self, s: str) -> List[List[str]]:result = []n = len(s)def is_palindrome(i: int, j: int) -> bool:"""判断s[i..j]（闭区间）是否为回文串"""while i < j:if s[i] != s[j]:return Falsei += 1j -= 1return Truedef backtrack(start: int, current_path: List[str]) -> None:"""递归回溯函数start: 当前分割的起始索引current_path: 已收集的回文子串列表"""# 终止条件：已分割完整个字符串if start == n:result.append(current_path.copy())  # 复制当前路径，避免后续修改影响结果return# 尝试从start到end的所有可能子串for end in range(start, n):# 若s[start..end]是回文串，则加入路径并继续分割剩余部分if is_palindrome(start, end):current_path.append(s[start:end+1])  # 加入当前回文子串backtrack(end + 1, current_path)     # 递归处理剩余部分current_path.pop()                   # 回溯：移除最后加入的子串# 从索引0开始，初始路径为空backtrack(0, [])return result