专栏首页架构说数据结构与算法:最长的回文子串

数据结构与算法:最长的回文子串

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

解题思路

代码

class Solution {
public:
    string longestPalindrome(string s) {
       
       int indexBegin =0;
       int indeEnd =0;
       int  n = s.size();

       //Palindrome

       //01 
      vector<vector<bool>> dp(n,vector<bool>(n,false)); //dp[start][end]  N>end >=start 


      //02 [aaa] 
      //[aaa] 
      //[aa]
      //[a]
      //if: s[start ] =s[end]  && 
      // /dp[start][end] = dp[start+1][end-1](一定存在) , end -1 >=start +1  

      //03 
       for(int end =0; end <n;end++)
       {
           for( int start =0; start <= end; start++)
           {
                 if (s[start] ==s[end])
                 {   //case1 
                     if(end -start >=2)
                     {
                          dp[start][end] = dp[start+1][end-1];
                     }else
                     {
                         //case2  i[0 -]
                         dp[start][end]  = true;
                     }
                 }
                  //回文子串 --最长的
                 if( dp[start][end]  == true && end-start > indeEnd- indexBegin )
                 {
                     indexBegin = start;
                     indeEnd = end;
                 }
           }
       }

       return s.substr(indexBegin,indeEnd-indexBegin+1);
    }
};

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-08-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最长回文子串——马拉车算法

    针对最长回文子串相关的问题,马拉车算法应该是比较通用的解法,今天我们就来具体看看这个算法。

    健程之道
  • LeetCode 1771. 由子序列构造的最长回文串的长度(最长回文子序)

    返回可按上述方法构造的最长 回文串 的 长度 。 如果无法构造回文串,返回 0 。

    Michael阿明
  • Go算法实战 - 5.【最长回文子串LeetCode-5】

    原题链接 https://leetcode-cn.com/problems/longest-palindromic-substring/

    junedayday
  • 《数据结构与算法》Day.1 最大子列和

    ———————————————— 版权声明:本文为博主「Sofar」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 ...

    风清醉
  • 【数据结构与算法面试题】子数组的最大和

    zhaozhiyong
  • 数据结构与算法-打印长方形算法

    cwl_java
  • 挑战数据结构和算法面试题——连续最长数字串

    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:字符串的处理,判断每一位是不是数字,用到了函数isd...

    zhaozhiyong
  • 算法面试题:超详细!如何找到字符串中的最长回文子串?

    小史:只要先对比第一个字符和倒数第一个字符,再对比第二个字符和倒数第二个字符,以此类推。如果都相等,那就是回文串了。

    帅地
  • Python算法与数据结构--求所有子数组的和的最大值

    题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

    用户1631416
  • PHP数据结构(七) ——串与实现KMP算法

    PHP数据结构(七)——串与实现KMP算法 (原创内容,转载请注明来源,谢谢) 一、定义 串是0个或多个字符组成的有限序列,任意连续字符组成的子序列称为子串,...

    用户1327360
  • 力扣 (LeetCode)-最大子序和,JavaScript数据结构与算法(数组)

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 疯子的算法总结(七) 字符串算法之 manacher 算法 O(N)解决回文串

    风骨散人Chiam
  • Js算法与数据结构拾萃(6):回溯

    对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,我们逐步构造更多的候选解,并且在确定某一...

    一粒小麦
  • 数据结构与算法——最小生成树

    在之前的文章中已经详细介绍了图的一些基础操作。而在实际生活中的许多问题都是通过转化为图的这类数据结构来求解的,这就涉及到了许多图的算法研究。

    五分钟学算法
  • 数据结构与算法——图最短路径

    最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。关于求解图的最短路径方法也层出不穷,本篇文章将详细讲解图的最短路...

    五分钟学算法
  • 【LeetCode】数据结构与算法 最短路径

    其实,8-10遍高频效果是最好的,这基本就是到另一个境界了。当然,大家没有那么多时间,3-5遍也可以去面试了。

    程序员小王
  • 数据结构与算法-图的存储结构

    设G=(V,E)是n个顶点的图,则G的邻接矩阵用n阶方阵G表示,若(Vi ,Vj )或< Vi ,Vj >属于E(G),则G[i][j]为1,否则为0。

    越陌度阡
  • 数据结构与算法—队列(搞懂最常用数据结构之一)

    按照上述的介绍,我们很容易知道数组实现的方式。用数组模拟表示队列。要考虑初始化,插入,问题。

    bigsai
  • 数据结构算法操作试题(C++/Python)——串联所有单词的子串

    leetcode 链接:https://leetcode-cn.com/problems/substring-with-concatenation-of-all...

    莫斯

扫码关注云+社区

领取腾讯云代金券