最长回文子串(LeetCode5.最长回文子串)

10月27日面试题

题目

截图自LeetCode

解析

中心展开法。
遍历字符串，每遍历到一个字符，以这个字符为中心向两侧展开，比较对称的字符是否相同，记录最长的回文子串。然后，再以这个字符与下一个字符的中间间隙为中心向两侧展开，因为偶数长度的子串也可能是回文子串，同样比较后记录下最长的回文子串。当遍历所有字符之后，返回记录的最长回文子串。时间复杂度O(n*n)。

代码

public String longestPalindrome(String str) {
    String result = ""; 
    if (str == null || str.length() < 1){
        return result;
    }
    for (int i = 0; i < str.length(); i++){
        //当前字符，两侧展开的起始下标
        int s = i; int e = i;
        while (s >=0 && e < str.length() && str.charAt(s) == str.charAt(e)){
            s--;
            e++;
        }
        result = str.substring(s + 1, e).length() > result.length()
            ? str.substring(s + 1, e) : result;
        //当前字符后的空隙，两侧展开的起始下标
        s = i; e = i + 1;
        while (s >=0 && e < str.length() && str.charAt(s) == str.charAt(e)){
            s--;
            e++;
        }
        result = str.substring(s + 1, e).length() > result.length()
            ? str.substring(s + 1, e) : result;
    }//for
    return result;
}