国外做微课的网站厦门网络推广培训
难度：中等
题目：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
解题思路：
使用回溯结合简单的回文检测来解决
- 定义辅助函数 isPalindrome:
- 这个函数用于判断一个字符串是否为回文串。
- 使用两个指针分别从字符串的头部和尾部向中心移动并比较字符是否相等。
- 定义递归函数 partition:
- 参数包括：
■ s: 原始输入字符串。
■ start: 当前处理的子串起始位置。
■ path: 用于存储当前递归路径上的回文子串。
■ result: 最终结果数组，用于收集所有满足条件的分割方案。 - 终止条件：当 start 等于字符串长度时，将 path 加入到结果数组 result 中。
- 递归逻辑：
- 遍历从 start 到字符串末尾的所有位置 i。
- 如果从 start 到 i 的子串是回文