当前位置：首页 > article >正文

Leetcode—5.最长回文子串【中等】

article 2025/1/11 7:45:23

2023每日刷题（三十五）

Leetcode—5.最长回文子串

在这里插入图片描述

中心扩展法算法思想

可以使用一种叫作“中心扩展法”的算法。由回文的性质可以知道，回文一定有一个中心点，从中心点向左和向右所形成的字符序列是一样的，并且如果字符串的长度为偶数的话，中心点在中间的两个字符的中间位置（不对应具体字符）；如果是奇数的话，则中心点会在中间的字符上。

实现代码

class Solution {
public:
    int findPalindrome(string s, int left, int right, int* start) {
        int len = s.size();
        while(left >= 0 && right <= len && s[left] == s[right]) {
            left--;
            right++;
        }
        left++;
        right--;
        *start = left;
        return right - left + 1;
    }

    string longestPalindrome(string s) {
        int n = s.size();
        int i = 0;
        int len1 = 0, len2 = 0;
        int start1 = 0, start2 = 0;
        int sta = 0;
        int maxlen = 0;
        while(i < n) {
            len1 = findPalindrome(s, i, i, &start1);
            len2 = findPalindrome(s, i, i + 1, &start2);
            if(len1 > maxlen || len2 > maxlen) {
                if(len1 > len2) {
                    sta = start1;
                    maxlen = len1;
                } else {
                    sta = start2;
                    maxlen = len2;
                }
            }
            i++;
        }
        return s.substr(sta, maxlen);
    }
};