腾讯常考十道算法真题：最长回文子串

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

实例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

这道题可以使用中心扩展法实现，从中间开始向两边扩散来判断回文串。

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是回文串可能是长度可能是奇数，也可能是偶数，因此需要加多一步：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和s[i+1] 为中心的回文串
    更新答案

完整代码如下：

class Solution {
    public String longestPalindrome(String s) {

        if(s==null|| s.length()<2){
             return s;
        }

        String result ="";
        for(int i=0;i<s.length();i++){
            String r1 = subLongestPalindrome(s,i,i);
            String r2 = subLongestPalindrome(s,i,i+1);
            String tempMax= r1.length()>r2.length()? r1 :r2;
            result = tempMax.length()> result.length()?tempMax:result;
            
        }
        return result;

    }

    private String subLongestPalindrome(String s,int l,int r){
        while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }

        return s.substring(l+1,r);
    }
}