• 题目：5. 最长回文子串
• 难度：中等
• 分类：字符串
• 解决方案：双指针
  

今天我们学习第5题最长回文子串，这是一个字符串的中等题，像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

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

示例1：

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

示例2：

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

分析

读完这道题后，我们发现一个新名词回文子串，什么是回文子串？首先我们先理解什么是回文串，就是从左向右读和从右向左读的结果是一样的字符串，如'abcba'。回文子串就是在给定字符串中寻找回文串。我们想想该如何寻找？

最简单直观的方法是遍历字符串，遍历的时候以每个字符为中心向左右两侧扩散。如图1所示。

图1.查找回文子串示意图

聪明的小伙伴们已经发现了上述解题思路对回文子串长度为偶数就不适用了，如示例2用上图的方法分析出来的结果就不正确。那该怎么办呢？解决办法很简单，对于奇数，我们以该字符为中心向两边扩散；对于偶数，我们以该字符和下一个字符作为中心字符，然后向两边扩散。具体见下面java代码所示：

class Solution {
    
    private int start = 0, maxLen = 0;
    
    public String longestPalindrome(String s) {
        if(s.length() < 1)
            return s;
        
        for(int i=0; i<s.length(); i++){
            // 回文子串为奇数时，查找最长回文子串
            extendPalindrome(s, i, i);
            // 回文子串为偶数时，查找最长回文子串
            extendPalindrome(s, i, i+1);
        }
        
        return s.substring(start, start + maxLen);
    }
    
    private void extendPalindrome(String s, int left, int right){
        // 判断是否为回文子串，若是，则左指针向左移动，右指针向右移动
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        
        // 回文子串查找完成后，判断刚刚查找的回文子串是否为最长回文子串，若是，则更新起始位置和最长长度
        if(maxLen < right-left-1){
            start = left + 1;
            maxLen = right -left - 1;
        }
    }
}

提交结果.png

整个算法流程的时间复杂度为O(n^2)，空间复杂度为O(1)。

Github地址

LeetCode-5 最长回文子串

参考链接

5.最长回文子串

更多文章，请扫描二维码关注『算法半岛』