首页 > 其他分享 >分割回文串 131

分割回文串 131

时间:2024-01-18 16:45:38浏览次数:45  
标签:分割 return string int cnt 131 分割线 backtracking 回文


这也是用回溯解决,回溯就是多层for循环,但是这一题有点难发现多层for循环体现在哪里。
实际上该问题for循环的层数与字符串的间隔有关
for循环的层数代表,分割线的个数;for循环的遍历代表这分割线的位置。
这里引用卡哥的图:

因为分割线不能取前一个的位置,所以要根据之前组合那题的套路,要引用startflag这个参数。
整体上还是脱离不了卡哥讲的那个框架。

点击查看代码
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

完整代码:

点击查看代码
class Solution {
public:
vector<string>v;
vector<vector<string>>cnt;
string temp;
bool huiwen(string s,int left,int right){
    while(left<=right){
        if(s[left]!=s[right]){return false;}
        ++left;
        --right;
    }
    return true;
}
void backtracking(string s,int startflag){
    if(startflag>=s.size()){
        cnt.push_back(v);
        return ;
    }
    for(int i=startflag;i<s.size();i++){
if(huiwen(s,startflag,i)){
    string str=s.substr(startflag,i-startflag+1);
    v.push_back(str);
}
else{continue;}
backtracking(s,i+1);
v.pop_back();
    }
}
    vector<vector<string>> partition(string s) {
backtracking(s,0);
return cnt;
    }
};

标签:分割,return,string,int,cnt,131,分割线,backtracking,回文
From: https://www.cnblogs.com/yun-che/p/17972828

相关文章

  • 回文字串
    回文串一般可以考虑把串倒过来思考问题对一个给定的串,我们将其倒序,设其长度为\(l\),求出原串和倒序的串的LCS,设长度为\(x\),则答案为\(l-x\)证明:我们假设已经获得了最终的回文串,然后我们将这个回文串倒序,那么肯定这个回文串与这个原串是相等的以样例为例其中红色字符是添加的......
  • 【论文笔记#2】Farseg++:用于高空间分辨率遥感图像地理空间对象分割的前景感知关系网络
    论文来源IEEETransactionsonPatternAnalysisandMachineIntelligence作者ZhuoZheng;YanfeiZhong;JunjueWang等发表年代2023使用方法多分支金字塔编码、前景-场景关系、前景感知解码、前景感知优化期刊层次CCFA;计算机科学1区;IF23.6原文链接......
  • 吴师兄学算法day07 双指针 680. 验证回文串 II
    题目:680. 验证回文串II易错点:s[1:3]是左闭右开我的第一次代码:classSolution(object):defvalidPalindrome(self,s):""":types:str:rtype:bool"""isPalindrome=lambdax:x==x[::-1]l......
  • Dithered golden interleaver 黄金分割伪随机交织器 代码备份
    目录公式来源DitheredgoldeninterleaverTheMatrix-DitheredGoldenInterleavingAlgorithm有错误欢迎指正公式来源DesignofaModifiedInterleavingAlgorithmBasedonGoldenSectionTheoryEnhancingthePerformanceofTurboCodesDitheredgoldeninterleaver(*......
  • 【CV】图像分割详解!
    图像分割是计算机视觉研究中的一个经典难题,已经成为图像理解领域关注的一个热点,图像分割是图像分析的第一步,是计算机视觉的基础,是图像理解的重要组成部分,同时也是图像处理中最困难的问题之一。所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交......
  • 吴师兄学算法day07 双指针 125. 验证回文串
    题目:125. 验证回文串易错点:isaplha()isdigit()lower()要熟悉,挺有用的。我的代码:classSolution:defisPalindrome(self,s:str)->bool:ans=''foriins:ifi.isalpha()ori.isdigit():ans+=i.lower()#......
  • 吴师兄学算法day07 双指针 9. 回文数
    题目:9. 回文数易错点:右指针要记得移动我的代码:classSolution:defisPalindrome(self,x:int)->bool:array=list(str(x))right=len(array)-1forleftinrange(len(array)//2):ifarray[left]==array[right]:......
  • [刷题班] LeetCode125. 验证回文串
    题目描述思路:左右指针只考虑数字和字母字母的话需要全部转化为小写然后使用左右指针判断是否是回文串方法一:classSolution{publicbooleanisPalindrome(Strings){List<Character>list=newArrayList<>();for(charc:s.toCharArray()){......
  • 深度学习3D网格分割网络---MeshCNN
    MeshCNN是2019年提出的直接在3DMesh上进行分类和分割的网络,MeshCNN在3D网格上定义了定义了卷积和池化层,依据三维模型边的连通关系将其转换为一个图来研究。最终能够在来自SHREC11数据集的30个类上达到98.6%的精度,并且在部件和人体数据集上有很好的分割性能。论文主页:https://ra......
  • 算法学习Day26组合总和、分割回文串
    Day26组合总和、分割回文串ByHQWQF2024/01/13笔记39.组合总和给定一个无重复元素的数组candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。说明:所有数字(包括target)都是正整数。解集......