每日一道leetcode：5. 最长回文子串-CSDN博客

本文链接：https://blog.csdn.net/google19890102/article/details/129475992

文章介绍了如何使用中心扩散法解决找到给定字符串中最长回文子串的问题。通过创建一个Solution类，实现cal方法来检测以特定位置为中心的回文子串，并在longestPalindrome方法中遍历字符串，比较不同中心的回文子串长度，从而找到最长的回文子串。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 题目（中等）

题目链接

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

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

示例 1：

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

示例 2：

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

提示：

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

2. 分析与题解

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

在这里插入图片描述

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

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);
    }
};