LetCode: 5. 最长回文子串

傷城~ 2022-04-18 01:53 109阅读 0赞

# 提示 #

LintCode中的相关算法题实现代码，可以在我的[GithHub][]中下载。

# 题目需求 #

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

**示例 1：**

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

**示例 2：**

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

# 解题思路 #

1.思想：

1）将子串分为单核和双核的情况，单核即指子串长度为奇数，双核则为偶数；

2）遍历每个除最后一个位置的字符index(字符位置)，单核：初始low = 初始high = index，low和high均不超过原字符串的下限和上限；判断low和high处的字符是否相等，相等则low++、high++（双核：初始high = 初始low+1 = index + 1）；

3）每次low与high处的字符相等时，都将当前最长的回文子串长度与high-low+1比较。后者大时，将最长的回文子串改为low与high之间的；

4）重复执行2）、3），直至high-low+1 等于原字符串长度或者遍历到最后一个字符，取当前截取到的回文子串，该子串即为最长的回文子串。

2.时间复杂度解释：

遍历字符：一层循环、O(n-1)；

找以当前字符为中心的最长回文子串：嵌套两个独立循环、O(2n\*(n-1)) = O(n^2)。

# 实现代码 #

class Solution {
          
         public String longestPalindrome(String s) {
            if(s.length()==0)
                return "";
           int start=0, end=0;
            for (int i = 0; i <s.length(); i++) {
                int i1 = expandAroundCenter(s, i, i);
                int i2 = expandAroundCenter(s, i, i + 1);
                int length= Math.max(i1,i2);
                if(length>end-start){
                    start=i-(length-1)/2;
                    end=i+length/2;
                }
            }
            return s.substring(start,end+1);
        }
    
       private int expandAroundCenter(String s, int i, int j){
            int left=i,right=j;
            while (left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            return right-left-1;
       }
    }

[GithHub]: https://github.com/Tjcug/LeetCode