开发者社区> sjf0115> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[网易]字符串回文分割

简介:
+关注继续查看

【题目】

将一个很长的字符串,分割成一段一段的子字符串,子字符串都是回文字符串。有回文字符串就输出最长的,没有回文就输出一个一个的字符。
例如:habbafgh
输出h,abba,f,g,h。

【思路一】

基于“最长回文子串算法”求出当前字符串的最长回文子串,就可以分成3部分
a、最长回文子串left部分
b、最长回文子串
c、最长回文子串right部分

然后分别求a和c的最长回文子串
递归至每部分都成单个字符+当前最长回文子串,就可以分解成最终结果。

【代码一】

#include<string>
#include<iostream>
using namespace std;

// beg end 用于返回最大回文串的范围
void MaxPalindromeNumber(string str,int& beg,int& end){
    int maxLen = 1,start = beg;
    int left,right;
    for(int i = beg;i <= end;i++){
        //奇数字串
        int oddLen = 1;
        left = i-1;
        right = i+1;
        while(left >= beg && right <= end && str[left] == str[right]){
            left--;
            right++;
            oddLen += 2;
        }
        //更新最大长度
        if(oddLen > maxLen){
            maxLen = oddLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
        //偶数字串
        left = i;
        right = i+1;
        int evenLen = 0;
        while(left >= beg && right <= end && str[left] == str[right]){
            left--;
            right++;
            evenLen += 2;
        }
        //更新最大长度
        if(evenLen > maxLen){
            maxLen = evenLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
    }
    beg = start;
    end = start + maxLen - 1;
}
int index = 0;
void SpilitPalindromeNumber(string str,int& beg,int& end){
    int lbeg = beg;
    int rend = end;
    //beg end 返回当前最大回文串的起始点和截止点
    MaxPalindromeNumber(str,beg,end);
    int lend = beg - 1;
    int rbeg = end + 1;
    // lbeg lend 最大回文串的左部
    // rbeg rend 最大回文串的右部
    if(lbeg <= lend){
        SpilitPalindromeNumber(str,lbeg,lend);
    }
    //控制格式输出
    if(index == 0){
        cout<<str.substr(beg,end-beg+1);
        index++;
    }
    else{
        cout<<","<<str.substr(beg,end-beg+1);
        index++;
    }
    if(rbeg <= rend){
        SpilitPalindromeNumber(str,rbeg,rend);
    }
}

int main(){
	string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
	int beg = 0;
	int end = str.length()-1;
	SpilitPalindromeNumber(str,beg,end);
	return 0;
}

【思路二】

先将给定字符串翻转,然后和原来的字符串一起,这样就变成了最长公共子序列问题。
此时可以利用动态规划的思路来完成。
关于最长公共子序列问题可以参考<算法导论>里面有详细的说明





相关链接:

[百度]2014百度校园招聘之最长回文串

[小米]2015小米校招之回文数判断

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
自媒体影视后期数字助理3--绿幕分割中间件设计
阿里云提供的线上AI能力在处理视觉信息方面已经有较为成熟和通用的产品,对于开始兴建媒体资源管理平台的自媒体来说,采用阿里云的AI能力、函数计算以及OSS等产品进行平台搭建可以快速实现建设与能力扩充。本文为SDR与HDR中间件的开发思路、技术架构设计和开发实战中参数的设置介绍,对一些数字影像的基础概念和阿里云视觉人工智能的API细节进行了分析。
0 0
算法赛推送-遥感图像语义分割
算法赛推送-遥感图像语义分割
0 0
竟然如此简单!输入明星名字就可以直接爬取高清图片
**听说你在自己喜欢的明星壁纸?比如李易峰,王一博,易烊千玺、王源、王俊凯,李现等。今天教你批量下载这些明星高清壁纸****(文末有福利)**
0 0
淘宝内容场下的人物理解系统
淘宝内容场下的人物理解系统
0 0
百度智能云过滤文本,图片
百度智能云过滤文本,图片
0 0
如何在视频里任意抠图?阿里工程师做到了!
小叽导读:现在的我们在手机上花费了越来越多的时间,其中,视频又格外地吸引我们的注意力。有很多好玩的视频,需要把前景物体从视频中分割出来,这需要花费创作者99%以上的时间。今天,阿里资深算法专家任海兵将告诉:阿里巴巴关于视频物体分割算法的三个方向与最新应用,希望对喜欢视频创作的你有所帮助。
0 0
+关注
sjf0115
Stay Hungry, Stay Foolish---我们必须用谦虚者的自觉,饥饿者的渴望的求职态度,来拥抱我们的未来。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
海量数据场景下的淘宝搜索智能——算法及实践
立即下载
海量数据场景下的淘宝搜索智能—算法及实践
立即下载
低代码开发师(初级)实战教程
立即下载