网站系统维护一般要多久,企业网站推广工具,推广平台网站,今天郴州刚刚发生的事LeetCode-131. 分割回文串【字符串 动态规划 回溯】 题目描述#xff1a;解题思路一#xff1a;回溯#xff0c; 回溯三部曲解题思路二#xff1a;0解题思路三#xff1a;0 题目描述#xff1a;
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个… LeetCode-131. 分割回文串【字符串 动态规划 回溯】 题目描述解题思路一回溯 回溯三部曲解题思路二0解题思路三0 题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1
输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2
输入s “a” 输出[[“a”]]
提示
1 s.length 16 s 仅由小写英文字母组成
解题思路一回溯 回溯三部曲
递归函数参数 全局变量数组path存放切割后回文的子串二维数组result存放结果集。 这两个参数可以放到函数参数里
本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。
在回溯算法求组合总和二 (opens new window)中我们深入探讨了组合问题什么时候需要startIndex什么时候不需要startIndex。
递归函数终止条件 从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。
那么在代码里什么是切割线呢
在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。
单层搜索的逻辑 来看看在递归循环中如何截取子串呢
在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文如果是回文就加入在vector path中path用来记录切割过的回文子串。
class Solution:def partition(self, s: str) - List[List[str]]:res []self.backtracking(s, 0, [], res)return resdef backtracking(self, s, index, path, res):if index len(s):res.append(path[:])returnfor i in range(index, len(s)):if s[index:i1] s[index:i1][::-1]: # 判断回文子串path.append(s[index:i1]) # 左闭右开self.backtracking(s, i1, path, res)path.pop()时间复杂度O(n2n) 空间复杂度O(n)
解题思路二0 时间复杂度O(n) 空间复杂度O(n)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
