最长回文字串

发表于

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”

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
class Solution {
public:
    int getNum(string s, int i, int j) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            i--;
            j++;
        }
        return j - i - 1;
    }
    string longestPalindrome(string s) {
         if (s.size() == 0)
            return s;
        int st = 0, e = 0;
        for (int i = 0; i < s.size() - 1; i++) {
            int len1 = getNum(s, i, i);
            int len2 = getNum(s, i, i+1);
            int len = max(len1, len2);
            if (len > e - st) {
                st = i - (len - 1) / 2;
                e = i + len / 2;
            }
        }
        return s.substr(st, e - st + 1);
    }
    
};