leetcode——5.最长回文子串

题目

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

示例 1：

输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

思路

最简单的方法，暴力破解，每一种情况都算一遍过去，循环时间复杂度为O(n^2)，验证是否回文又需要O(n)的时间复杂度，妥妥的超时，因此需要进行优化。

定义dp[i][j]表示从第i个字符到第j个字符是否为回文，则：

dp[i][j] = true i = j，即当前查找字符串长度为1时

dp[i][j] = s[i] == s[j] j-i = 1，即当前查找字符串长度为2时

若查找的字符串长度大于2时，只需要知道i+1到j-1是否回文，是的话，则比较s[i],s[j]，不是的话，dp[i][j]也必定不为回文，即

dp[i][j] = dp[i+1][j-1] and s[i] == s[j]

动态规划递推式已求出，时间复杂度为O(n^2)，

空间复杂度为O(n^2)，空间复杂度上还可以继续优化。

代码如下：

class Solution {
    public String longestPalindrome(String str) {
        if(str.length() == 0){
            return "";
        }
        //最大起点和终点
        int maxS = 0,maxE = 0;
        int maxLen = 0;
    
        int len = str.length();
        boolean dp[][] = new boolean[len+1][len+1];
        for(int i = 1; i <= len; i++){
            for(int s = 0; s < len; s++){
                int e = s + i -1;
                //终点越界
                if(e >= len){
                    break;
                }
                if(i == 1){
                    dp[s][e] = true;
                }
                else if(i == 2){
                    dp[s][e] = str.charAt(s) == str.charAt(e);
                }else{
                    dp[s][e] = dp[s+1][e-1] && str.charAt(s) == str.charAt(e);
                }
                
                if(dp[s][e] && i > maxLen){
                    maxLen = i;
                    maxS = s;
                    maxE = e;
                }
            }
        }
        
        return str.substring(maxS,maxE+1);
    }

}
           

参考网上的代码，此题还可以采用中心扩展的方法求解，大体思路为，选定一个中心点mid，向两边扩展，直到s[mid-1] != s[mid+1]，返回长度。

中心点数量为2n-1, 若字符串长度为奇数，中心点只有一个mid，此时中心点有n个，，若长度为偶数，则应该选取mid和mid+1为中心点，此时中心点有n-1个。

此种方法时间复杂度为O(n^2)，空间复杂度为O(1)，代码就不贴了。

所讲之处如有错误，还望指出，谢谢观看。