【LeetCode5】最大回文子串(中心扩散法)

【LeetCode5】最大回文子串(中心扩散法),第1张

【LeetCode5】最大回文子串(中心扩散法) 一、题目


提示:

1 <= s.length <= 1000s 仅由数字和英文字母(大写和/或小写)组成 二、思路

中心扩散法。

从每个节点开始,当前结点向两边扩散来判断回文串,因为回文串长度可能是奇数或者偶数,即后者就木有一个中心字符,伪代码应该如下:

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

我们通过传入的左指针l和右指针r,可以同时处理回文串为奇数和偶数的情况。注意palindrome函数最后的s.substr(l+1, r-1-l)中,右边界是相对下标,其计算是:(r-1)-(l+1)+1=r-l-1。

三、代码
class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        for(int i = 0; i < s.size(); i++){
            //以s[i]为中心的最长回文子串
            string s1 = palindrome(s, i, i);
            //以s[i]和s[i+1]为中心的最长回文子串
            string s2 = palindrome(s, i, i + 1);
            //ans = longest(ans, s1, s2)
            if(ans.size() < s1.size()){
                ans = s1;
            }
            if(ans.size() < s2.size()){
                ans = s2;
            }
        }
        return ans;
    }
    string palindrome(string& s, int l, int r){
        //防止索引越界
        while(l >= 0 && r < s.size() && s[l] == s[r]){
            //向两边展开
            l--;r++;
        }
        return s.substr(l + 1, r - l - 1);
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5713690.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存