最长回文子串

题目描述

  给定一个字符串s,找到s中最长的回文子串。

输入输出样例

Input: s = "babad"
Output: "bab"

  对于这样一个字符串，不止存在一个最长回文子串。可以是bab或aba。

题解

  对于这个题目，如果使用翻转的话。对于aacxycaa,反转之后是aacyxcaa,这时最长公共子串为aac,但是正确的回文子串为aa，所以这种方法不可以使用。
  这个题目，应该思考如何使用双指针。对于寻找回文串的问题的关键之处在于：从中间开始向两边扩散来判断。首先我们需要先找到这个最长字符串，但是对于字符串来说，它们的个数可能是奇数或是偶数。对于偶数来说，寻找s[i]为中心的回文串；对于奇数，寻找s[i]和s[i+1]为中心的回文串。在寻找的过程中，应该注意边界限制。具体代码如下

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i <s.size(); i++) {
            //以s[i]为中心的最长回文子串
            string s1 = Palindrome(s,i,i);
            //以s[i+1]为中心的最长回文子串
            string s2 = Palindrome(s,i,i+1);

            // res = longest(res,s1,s2);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }
        return res;
    }
    string Palindrome(string& s,int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            // 向两边展开
            l--,r++;
        }

        // 返回以 s[l] 和 s[r]为中心的最长字符串
        return s.substr(l+1, r-l-1);
    }
};