难度: Medium
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
Submission
运行时间: 156 ms
内存: 31.8 MB
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
def backtrack(path, begin):
if begin == len(s):
result.append(list(path))
return
for cut_length in range(1, len(s)-begin+1):
cut_s = s[begin:begin+cut_length]
if cut_s != cut_s[::-1]:
continue
path.append(cut_s)
begin += cut_length
backtrack(path, begin)
begin -= cut_length
path.pop()
backtrack([], 0)
return result
Explain
这个题解使用回溯法来解决分割回文串的问题。它从字符串的起始位置开始，尝试将字符串切割成不同长度的子串，并判断每个子串是否为回文串。如果子串是回文串，就将其加入当前的分割方案中，并递归地对剩余的字符串进行分割。当到达字符串的末尾时，将当前的分割方案加入最终结果中。通过回溯的方式，可以枚举所有可能的分割方案。
时间复杂度: O(n * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
def backtrack(path, begin):
# 如果已经处理完整个字符串，将当前分割方案加入结果中
if begin == len(s):
result.append(list(path))
return
# 尝试将字符串切割成不同长度的子串
for cut_length in range(1, len(s)-begin+1):
cut_s = s[begin:begin+cut_length]
# 如果子串不是回文串，跳过
if cut_s != cut_s[::-1]:
continue
# 将回文子串加入当前分割方案
path.append(cut_s)
# 递归处理剩余的字符串
begin += cut_length
backtrack(path, begin)
# 回溯，将最后一个加入的子串移除，尝试其他分割方案
begin -= cut_length
path.pop()
backtrack([], 0)
return result
Explore
使用`cut_s != cut_s[::-1]`进行回文判断是因为它是一种简单且直接的方法。在字符串长度较短时，这种方法的效率通常是可接受的。虽然存在更优化的判断方法，如动态规划预处理所有子串的回文性质，然而这需要额外的时间和空间复杂度进行预处理。对于LeetCode题目的解决方案，通常优先考虑代码的简洁性和直观性，特别是在不严重影响性能的情况下。
在回溯过程中使用`begin += cut_length`和`begin -= cut_length`是为了控制当前递归的深度和位置，确保每次递归正确地处理字符串的剩余部分。这种方法虽然直接，但可以通过传递新的`begin`值给递归调用来优化，从而避免修改和恢复`begin`值，这样做可以让代码更清晰。例如，调用`backtrack(path, begin + cut_length)`代替原有的操作。
在当前的回溯算法中，确实可能存在一些重复计算，特别是对于那些非回文子串的检查。一种更高效的处理方式是使用动态规划或者记忆化搜索来存储已经计算过的结果（例如子串是否为回文），从而避免在递归中重复相同的计算。此外，预先计算并存储所有子串的回文性质也是一个优化的选择。
对于最大长度为16的字符串，这种回溯算法在最坏情况下的时间复杂度是指数级的，因为每个位置都可以是多个回文分割点。然而，由于字符串长度相对较短，即便是指数级时间复杂度，实际的计算量也是可接受的。因此，对于长度限制在16以内的问题，这种回溯算法是适合解决实际问题的。