回溯算法练习——5、分割回文串（C++和Python描述）_回溯法解决分割串问题python

作者：小小林熬夜学编程 | 2024-06-05 14:00:20

踩

回溯法解决分割串问题python

来源：代码随想录
本题的力扣链接：https://leetcode-cn.com/problems/palindrome-partitioning/

目录

1、题目描述：

2、思路：

3、代码：

3.1 python代码：

3.2 C++代码：

4、总结：

1、题目描述：

在这里插入图片描述

在这里插入图片描述

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

但是，还是和组合不太一样，我们收集的元素是啥呢？其实就是路径上的元素，和组合一样，只不过这个时候不是收集一个元素，而是字符串的子集。

只要是把这个树能画出来，我们就知道怎么用回溯法做了，按回溯的模板和递归三部曲来：

在这里插入图片描述

注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

class Solution:
    def partition(1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/676798