首页 > 其他分享 >每日一道leetcode:5. 最长回文子串

每日一道leetcode:5. 最长回文子串

时间:2023-06-14 19:34:31浏览次数:48  
标签:子串 int max len 字符串 left leetcode 回文


1. 题目(中等)

题目链接

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

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。

示例 2:

输入:s = “cbbd”
输出:“bb”

提示:

  • 1 <= s.length <= 1000
  • s仅由数字和英文字母组成

2. 分析与题解

首先从回文字符串的定义可以知道,沿着中心轴翻转,则翻转前后的字符串是相同的,如:

每日一道leetcode:5. 最长回文子串_leetcode

换言之,对于中心轴两边的值是相等的,考察的知识点是中心扩散法,沿着中心轴向两端扩散,这也是回文串的主要判断方法,即头尾两个指针向两端移动,并判断两个指针处的值是否相等。

class Solution {
public:
    vector<int> cal(string s, int i, int j) {
        int n = s.length();
        while (i >= 0 && j < n && s[i] == s[j]) {
            i --;
            j ++;
        }
        return {i+1, j-1};
    }

    string longestPalindrome(string s) {
        int n = s.length();
        int left = 0, right = 0;
        int max_len = 0;
        for (int i = 0; i < n; i++) {
            vector<int> a = cal(s, i, i);
            vector<int> b = cal(s, i, i+1);
            if (a[1]-a[0]+1 > max_len) {
                left = a[0];
                right = a[1];
                max_len = a[1]-a[0]+1;
            }
            if (b[1]-b[0]+1 > max_len) {
                left = b[0];
                right = b[1];
                max_len = b[1]-b[0]+1;
            }
        }
        return s.substr(left,right-left+1);
    }
};


标签:子串,int,max,len,字符串,left,leetcode,回文
From: https://blog.51cto.com/u_16161414/6480211

相关文章

  • Leetcode
    1.两数之和题目链接:1.两数之和-力扣(LeetCode)给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target 的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意......
  • [LeetCode] 1348. Tweet Counts Per Frequency 推文计数
    Asocialmediacompanyistryingtomonitoractivityontheirsitebyanalyzingthenumberoftweetsthatoccurinselectperiodsoftime.Theseperiodscanbepartitionedintosmaller timechunks basedonacertainfrequency(every minute, hour,or day......
  • Leetcode 常见报错的原因分析
    问题1问题描述Line522:Char69:runtimeerror:applyingnon-zerooffset18446744073709551615tonullpointer(basic_string.h)报错原因stringres=0报错分析这里报错的原因是因为使用了int整型变量来初始化string。......
  • Log in Leetcode in Vscode With Cookies" #标题
    Installleetcodeplug-ininvscodeIt'seasybysearchinExtension.LoginwithcookiesIfyouwanttologinleetcodeinvscodeleetcodeplug-inbygithubaccount,theremaybebugsthatyoucan'ttestorsubmit.Butifyousigninwithcookies......
  • Vscdoe 通过cookie 登陆美区 LeetCode
    安装插件vscode安装leetcode插件。使用cookie登陆如果选择使用github登陆leetcode.com,似乎会有无法提交和测试的bug,而用cookie登陆就没有这个问题使用edge获取cookie使用Firefox获取的cookie有问题,无法正常登陆右键,选择检查选择网络打开leetcode的problem页面下滑找到......
  • #yyds干货盘点# LeetCode程序员面试金典:被围绕的区域
    题目:给你一个mxn的矩阵board,由若干字符'X'和'O',找到所有被'X'围绕的区域,并将这些区域里所有的 'O'用'X'填充。 示例1:输入:board=[["X","X","X","X"],["X","O","O",&quo......
  • 图解LeetCode——994. 腐烂的橘子
    一、题目在给定的 mxn 网格 grid 中,每个单元格可以有以下三个值之一:值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,腐烂的橘子 周围 4个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果......
  • Leetcode常见报错的原因分析
    问题1问题描述Line522:Char69:runtimeerror:applyingnon-zerooffset18446744073709551615tonullpointer(basic_string.h)报错原因stringres=0报错分析这里报错的原因是因为使用了int整型变量来初始化string。......
  • leetcode-70 爬楼梯(java实现)
    爬楼梯题目分析1递归写法动态规划解法题目假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?分析1递归写法如果要爬上第n阶,要么是从第n-1上面再爬1阶上去的,要么是从n-2上面再爬2阶上去的,那么我们就可以想到f(n)=......
  • leetcode 104. 二叉树的最大深度(java实现)
    104.二叉树的最大深度标题解法标题给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。解法publicclassSolution{publicintmaxDepth(TreeNoderoot){//如果节点为空,返回深度为0......