前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++代码算法题:(5).最长回文子串

C++代码算法题:(5).最长回文子串

作者头像
全栈程序员站长
发布2022-06-29 10:19:07
2890
发布2022-06-29 10:19:07
举报
文章被收录于专栏:全栈程序员必看

大家好,又见面了,我是你们的朋友全栈君。

题目及要求:

给你一个字符串 s,找到 s 中最长的回文子串。

提示:

1 <= s.length <= 1000 s 仅由数字和英文字母(大写和/或小写)组成

原创代码:

代码语言:javascript
复制
class Solution { 
   
public:
    string longestPalindrome(string s) 
    { 
   
        int begin=0;//每个当前子串的开头
        int end=0;//每个当前子串的末尾
        int value=0;//判断条件使用。条件一:当形参string s不存在两个及两个以上元素个数的回文字串则value=1,条件二:当形参string s存在两个及两个以上元素个数的回文字串则value=0
        int max=0;//记录历史回文字串的最大元素个数
        string str;//代表当前回文串
        string str_2=s[0];//代表最大回文串
        for(begin=0;begin<=s.size()-1;begin++)
        { 
   
            for(end=begin;end<=s.size()-1;end++)
            { 
   
                value=0;
                /*条件一:当形参string s不存在两个及两个以上元素个数的回文字串则value=1*/
                for(int i=0;i<=(end-begin)/2;i++)
                { 
   
                    if(s[begin+i]!=s[end-i])
                    { 
   
                        value=1;
                        break;
                    }
                }
                /*条件二:当形参string s存在两个及两个以上元素个数的回文字串则value=0*/
                if(value==0)
                { 
   
                    str.erase(0,str.size());
                    for(int i=begin;i<=end;i++)
                    { 
   
                        str.push_back(s[i]);
                    }
                    str_2=str.size()>max?str:str_2;
                    max=str.size()>max?str.size():max;
                    if(str_2.size()==s.size())
                    return str_2;
                }
            }
        }
        return str_2;
    }
};

输出示例:

示例 1: 输入:s = “babad” 输出:“bab” 解释:“aba” 同样是符合题意的答案。 示例 2: 输入:s = “cbbd” 输出:“bb” 示例 3: 输入:s = “a” 输出:“a” 示例 4: 输入:s = “ac” 输出:“a”

代码思路:

首先: 定义变量,并将str_2用s[0]赋初值,用以当形参string s不存在两个及两个以上元素个数的回文字串则输出形参s的首元素

int begin=0;//每个当前子串的开头 int end=0;//每个当前子串的末尾 int value=0;//判断下一个字符是否属于当前子串 int max=0;//记录历史回文子串的最大元素个数 string str;//代表当前回文子串 string str_2=s[0];//代表最大回文子串

其次: 每一个子串(形参s元素s[begin]至s[end]之间的元素)都先判断条件一(当前子串是否存在两个及两个以上元素个数的回文字串)是否满足。若满足条件一,则进行

value=1; break;

则str_2的值不改变为初值s[0],接下来继续进行循环

end++

如果当前子串(形参s元素s[begin]至s[end]之间的元素)不满足条件一,则由于此时

value=0;

则直接进入条件二来将str(形参s元素s[begin]至s[end]之间的元素)重新赋值(注意str表示当前的回文子串)并通过变量max来判断当前回文子串str与历史最大回文子串str_2的元素进行比较,如果当前回文子串str元素个数比历史最大回文子串str_2的元素个数更大则将历史最大回文子串str_2重新赋值 注意接下来的语句是用来缩小程序运行时间的

if(str_2.size()==s.size()) return str_2;

接下来继续进行循环

end++

最后: 当满足begin>s.size()-1时退出程序,执行

return str_2

反思所得:

在这道题的解题过程中,我开始的时候是不明白回文的定义是什么的,但是经过代码的不断上传和查看他人的讲解,我明白了回文的定义(类似于“上海自来水来自海上”),了解了回文的定义我就重新修改了思路,为了简便算法,我开始考虑将程序分条件编程,并且在每个条件内尽量减少程序进行无用的部分。

LeetCode链接:

https://leetcode-cn.com/problems/longest-palindromic-substring/

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/132343.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目及要求:
  • 提示:
  • 原创代码:
  • 输出示例:
  • 代码思路:
  • 反思所得:
  • LeetCode链接:
相关产品与服务
云开发 CloudBase
云开发(Tencent CloudBase,TCB)是腾讯云提供的云原生一体化开发环境和工具平台,为200万+企业和开发者提供高可用、自动弹性扩缩的后端云服务,可用于云端一体化开发多种端应用(小程序、公众号、Web 应用等),避免了应用开发过程中繁琐的服务器搭建及运维,开发者可以专注于业务逻辑的实现,开发门槛更低,效率更高。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档