首页 > 其他分享 >5. 最长回文子串

5. 最长回文子串

时间:2024-05-22 16:52:47浏览次数:25  
标签:子串 right end start 回文 最长 left

给你一个字符串 s,找到 s 中最长的
回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        if(n<2)
        {
            return s;
        }
        int start=0;
        int end=0;
        for(int i=0;i<n;i++)
        {
            int left=i;
            int right=i;
            while(left>=0&&right<n&&s[left]==s[right])
            {
                if(right-left+1>end-start+1)
                {
                    end=right;
                    start=left;
                }
                left--;
                right++;
            }
            left=i;
            right=i+1;
            while(left>=0&&right<n&&s[left]==s[right])
            {
                if(right-left+1>end-start+1)
                {
                    end=right;
                    start=left;
                }
                left--;
                right++;
            }
        }
        return s.substr(start,end-start+1);
    }
};

标签:子串,right,end,start,回文,最长,left
From: https://www.cnblogs.com/donghao99/p/18206639

相关文章

  • 300-Longest Increasing Subsequnce-最长递增子序列
    问题描述链接:https://leetcode.com/problems/longest-increasing-subsequence/description/Givenanintegerarray nums,return thelengthofthelongest strictlyincreasing subsequence解释:给定一个数组nums,返回长的严格递增子序列。案例:Input:nums=[10,9,......
  • 5-Longest Palindromic Substring-最长回文串
    问题描述链接:https://leetcode.com/problems/longest-palindromic-substring/description/Givenastring s,return thelongest palindromicsubstringins解释:给定一个字符串,求其最长的回文串回文串:一个字符串,如果从左往右读和从左往右读读出来的序列是一样的,称......
  • CSP历年复赛题-P1015 [NOIP1999 普及组] 回文数
    原题链接:https://www.luogu.com.cn/problem/P1015题意解读:一个N进制数M,把M正序和M逆序相加,几次之后得到是数是回文数,如果超过30次还无法得到回文数,输出Impossible!。解题思路:M最长100位,因此需要高精度,定义数组vector<int>m来存储整数M注意:16进制中可能存在'a~f''A~F'等字母,需......
  • 【每周例题】判断回文串
    判断回文串题目给你一个字符串 x ,如果 x 是一个回文字符串,返回 true ;否则,返回 false 。回文字符串是指正序(从左向右)和倒序(从右向左)读都是一样的。例如,aba 是回文,而 abc 不是。代码#include<bits/stdc++.h>#include<cstring>usingnamespacestd;intmain(){......
  • 300. 最长递增子序列
    给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1:输入:nums=[10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是[2,3,7,1......
  • 有效回文 II
    题目链接:来自罗勇军《算法竞赛》尺取法一节的习题。思路:反向扫描,设双指针为\(i\)和\(j\)。if(s[i]==s[j])i++,j--;否则的话要么删除\(s[i]\)或者删除\(s[j]\),看剩下的字符串是否是回文串。classSolution{public:boolcheck(stringstr,intl,intr){......
  • P1807 最长路
    链接:https://www.luogu.com.cn/problem/P1807其实没什么难的,注意点:拓扑排序,把非1的入度为0的点及其衍生点全删了,不然会到一半无法拓扑下去。关键在于我之前那个删点的操作,先看错误代码:...voidclearpoint(llix){ for(lli=0;i<G[ix].size();i++) { rd[G[ix][i]]-......
  • ABC353E字典树处理最长公共前缀
    https://atcoder.jp/contests/abc353/tasks/abc353_e其实就是字典树板子题。似乎遇到最长公共前缀,就该想到字典树。依次加入每个字符串:维护一个数组siz来统计在当前串之前的串在对应点的出现次数。手模一下字典树的建树过程,显然如果当前串\(S_i\)能跑到一个曾经串\(S_......
  • 输出最长的单词
    输入一行字符,输出最长的单词。#include<stdio.h>#include<string.h>#defineN100intLongestVoc(charstr[]);intAlpha(charc);intmain(void){charstr[N];printf("pleaseinputastring:");gets(str);intpos=LongestVoc(str);pri......
  • 【每日一题】最长回文子串
    5.最长回文子串给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s仅由数字和英文......