最长回文子串

佚名 7年前 (2019-04-21) 随笔 1131人围观抢沙发百度已收录

题目：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"
看到这个题目，我们先来举例子来分析一下，比如：
　　　　babad -> bab/aba    //称为单核的情况
　　　　abcbadb -> abcba　　//也是单核的情况
　　　　abcddcbaf -> abcddcba　　//是双核的情况
从上面例子的结果我们可以看出：
　　1.回文子串个数有奇数和偶数，需要分开。
　　2.我们可以看到回文子串是对称的。
　　3.确定用中心扩展法找。
代码如下：

class Solution {
    private static int maxLen = 0;
    private String sub = "";
    public String longestPalindrome(String s) {
        if(s.length() == 0){
            return "";
        }
        if(s.length() == 1){
            return s;
        }
        for(int i = 0;i < s.length();i++){
            findlongestPalindrome(s,i,i);  //单核的情况
            findlongestPalindrome(s,i,i+1); //双核的情况
        }
        return sub;
    }
    
    public void findlongestPalindrome(String s,int low,int high){
        while(low >= 0 && high <= s.length() - 1){
            if(s.charAt(low) == s.charAt(high)){
                if(high - low + 1> maxLen){
                    maxLen = high - low + 1;
                    sub = s.substring(low,high + 1);
                }
                low--;
                high++;
            }else{
                break;
            }
        }
    }
}