5. 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/description/

前置知识

取字符串的子串

s.substr(start,len);
// start是子串的起始位置，从0开始，len是子串的长度
1
2

---

思路

枚举回文字符串的中间位置i，如果回文字符串的长度为奇数，则从左右i-1,i+1两个方向遍历字符串，判断是否满足两者字符相等的情况。如果是偶数，则从i,i+1遍历字符串即可，判断是否满足两者字符相等的情况。

需要注意的是，有效回文字符串的区间为[l+1, r-1]，因为当两者不相等的时候已经进行了一次运算，而给定区间[l, r]，其长度为r - l + 1

---

代码

class Solution {
public:
    string longestPalindrome(string s) {
        string res;

        // 遍历中心点
        for (int i = 0; i < s.size(); i ++){
            // 回文字符串长度为奇数
            int l = i - 1, r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]){
                l --;
                r ++;
            }
            if (res.size() < (r - l - 1)) res = s.substr(l + 1, r - l - 1);

            // 回文字符串长度为偶数
            l = i, r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]){
                l --;
                r ++;
            }
            if (res.size() < (r - l - 1)) res = s.substr(l + 1, r - l - 1);

        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28