欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode5-Longest Palindromic Substring(回文)

程序员文章站 2022-03-11 12:53:09
...

题目: https://leetcode.com/problems/longest-palindromic-substring/

概述: 求长回文串

思路: 一个for循环,i为下标,我们以这个i为中心,向两边辐射,看最长的回文串能有多长。记住要考虑两种情况:①要求的最长回文串为偶数个 ②要求的回文串为奇数个。 这点会在传参中体现。

class Solution {
public:
    int lo, max_len = 0;
    string longestPalindrome(string s) {
        int len = s.size();
        if(len < 2) return s;
        for(int i = 0; i < s.size() - 1; i++)
        {
            checkPalindrome(s, i, i);
            checkPalindrome(s, i, i + 1);
        }
        return s.substr(lo, max_len);
    }
    
    void checkPalindrome(string s, int i, int j)
    {
        while(i >= 0 && j < s.size() && s[i] == s[j])
        {
            i--;
            j++;
        }
        if(max_len <= j - i - 1)
        {
            lo = i + 1;
            max_len =  j - i - 1;
        }
    }
};