leetcode--5--最长回文子串

题目：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

链接：https://leetcode-cn.com/problems/longest-palindromic-substring

思路：
1、这道题可以采用中心拓展法，即从一个中心向两边进行拓展，确保找到满足条件的最长的回文子串
2、这里定义了一个expand函数来进行中心拓展，分别往两边进行拓展，从而找到最长的回文串
3、这里用了一种很巧妙的方法，按照奇偶的方式对字符串的每一次迭代进行中心拓展

Python代码：

class Solution(object):

    def expand(self, s, i, j):
        while (i>=0 and j<len(s) and s[i]==s[j]):
            i-=1
            j+=1
        return s[i+1:j]

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return ""
        
        ret = s[0]

        for i in range(len(s)):
            odd = self.expand(s,i,i)
            even = self.expand(s,i,i+1)
            ret = max(odd,even,ret,key=len)
        return ret

C++代码：

class Solution {
public:

    string expand(string s, int i, int j){
        while(i>=0 && j<s.size() && s[i]==s[j]){
            i -= 1;
            j += 1;
        }
        return s.substr(i+1, j-i-1);
    }

    string longestPalindrome(string s) {
        if(s.size()==0) return "";

        string ret = s.substr(0, 1); // 由于ret需要定义成string类型，所以这里需要用substr来获取第一个字符
        for (int i=0; i<s.size(); i++){
            string odd = expand(s, i, i);
            string even = expand(s, i, i+1);
            if (odd.size() > ret.size()){
                ret = odd;
            }
            if (even.size() > ret.size()){
                ret = even;
            }
        }
        return ret;
    }
};