首页 > 其他分享 >奇怪的回溯增加了 | leetcode131分割回文串

奇怪的回溯增加了 | leetcode131分割回文串

时间:2024-03-16 20:33:08浏览次数:20  
标签:分割 示例 leetcode131 startIndex 回溯 回文

题目要求:给你一个字符串 s,请你将s分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案

示例 1:

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

示例 2:

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

上述为常规做法,这里回溯的时候是i+1的,就很正常

 这是我第一次做的时候自己憋出来的,在第一次我让i=startIndex,这时切割总是会出空串,为此我在isTrue中增加了如果是空则返回false,然后我发现这样做i在第一轮的时候永远是空过的,如果再使用backtracking(i+1)

那就相当于startIndex其实是startIndex+2。 因此这里的i其实是在for内就已经完成了+1,不能再在回溯的时候+1。主要是保证startIndex每一轮只+1,树层才可以正常的逐级增长。

 

结语:回溯法画树确实能让人想清楚结构和过程

标签:分割,示例,leetcode131,startIndex,回溯,回文
From: https://www.cnblogs.com/kun1790051360/p/18077550

相关文章

  • 搜索与回溯算法
    排列#include<cstdio>#include<iostream>#include<algorithm>#include<iomanip>intvis[25],ans[25];intn;usingnamespacestd;voiddfs(intdep){if(dep==n+1){for(inti=1;i<=n;i++)cout<<setw(......
  • Leetcode刷题-动态规划-最长回文子串
    链接:5.最长回文子串-力扣(LeetCode)给你一个字符串s,找到s中最长的回文子串,如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s......
  • 125. 验证回文串c
    回文串置逆,栈,双指针。booljudge(charc){if(c>='a'&&c<='z')returntrue;if(c>='A'&&c<='Z')returntrue;if(c>='0'&&c<='9')returntrue;return......
  • 234. 回文链表c
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*pre;booljudge(structListNode*head){if(!head)returntrue;booltemp=judge(head->next);if(!temp)r......
  • 回溯:排列回溯和组合回溯的区别
    在形式上,最明显的问题就是[1,2]和[2,1]这两个list在排列中是正确的,而在组合中一般只有前者排列回溯注重元素的顺序,并且允许重复元素的出现,而组合回溯则不考虑元素的顺序。排列回溯:通常使用一个boolean数组来标记哪些元素已经被选择,哪些尚未被选择在递归的每一层,我们......
  • 信息学奥赛一本通:1146:判断字符串是否为回文
    【题目描述】输入一个字符串,输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。【输入】输入为一行字符串(字符串中没有空白字符,字符串长度不超过100)。【输出】如果字符串是回文,输出yes;否则,输出no。【输入样例】abcdedcba【输出样例】yes【参考程序......
  • 回文树
    例题HDU-5421翻译如果字符串是静态的,则可以使用Manacher算法。但本题的字符串可以动态在首位添加字符,无法使用Manacher。本题可以使用回文树(回文自动机)算法。该算法的时间复杂度为\(\mathcal{O}(N)\),但空间复杂度较差,因为其本质上是字典树。1回文树的关键技术回文树的......
  • leetcode回溯法典型例题:39.组合总和、40组合总和 II、46.全排列、47.全排列 II
    leetcode回溯法典型例题:39.组合总和、40组合总和II、46.全排列、47.全排列II39.组合总和39.组合总和-力扣(LeetCode)思路构建组合使用递归的方式构建出所有组合。由题意可知,元素可以无限取用,所以我们构建的时候每确定一个数字,进入更深层递归的时候,每个数字都可以取用(此......
  • 回文自动机学习笔记
    回文自动机学习笔记定义所谓自动机,是一个对信号序列进行判定的数学模型。即对一连串有顺序的信号关于某一个判定给出或真或假的判定。所谓回文自动机,就是对一个字符串进行其是否为回文串的判定。也就是存储字符串\(s\)中的所有的回文串。与\(\text{SA}\)不同的是,\(\text{SA......
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ
    思路分析:使用DFS算法进行全排列,递归地尝试每个可能的排列方式。使用path向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。使用numvisited向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。在递归过程中,对于每个未访问的......