算法训练 | 回溯思想 044.20（分割回文串）

文章目录

• 7. 分割回文串
• • 7.1 题目
• • • 7.2 解法：采用回溯算法进行字符串分割

• • • • 具体思路如下：
        （1）函数的返回值与参数设置
        （2）终止条件设定
        （3）遍历过程详细说明

      • 7.2.2代码

7.分割回文串

7.1题目

给定输入字符串 s，请你完成对 s 的分割操作，确保每个子串均为 回文串 。请列出所有可能的分割方案。

• 示例一：

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

• 示例二：

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

7.2解法：回溯

7.2.1回溯思路

例如对于字符串abcdef：

• 组合型问题：从字母表中依次选择并切除第一个a后，在剩下的五个字母表（即bcdef）中继续选择并切除下一个字符；若选中b，则在剩下的五个字符（即cdef）中继续选择并切除下一个字符……
• 切割型问题