LeetCode 5. Longest Palindromic Substring

题目描述：

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

解析：求解一个字符串的最长回文子串。

解法1：双指针法

采用双指针，从中心往两端进行扩散，判断两个指针所指向的字符是否相等。需要考虑子串长度是奇数和偶数的情况。

代码如下：

class Solution {
public:
    string palindrome(string s, int left, int right){
        while(left >=0 && right < s.length() && s[left] == s[right])
        {
            left --;
            right ++;
        }
        return s.substr(left+1, right-left-1);
    }
    string longestPalindrome(string s) {
        string res = "";
        int len = s.length();
        for(int i=0; i< len; i++){
            // 以 s[i] 为中心的最长回文子串
            string s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            string s2 = palindrome(s, i, i+1);
            res = res.length() > s1.length() ? res:s1;
            res = res.length() > s2.length() ? res:s2;
        }
        return res;
    }
};