面试高频算法题---最长回文子串

目录

题目

题目分析

代码实现

代码解析

复杂度分析

---

题目

题目链接：最长回文子串

给一个字符串s，找到s中最长的回文子串

题目分析

所谓回文就是“雾锁山头山锁雾”，“天连水尾水连天” ，就是正着和反着是一样的

比如“abcdcba”，我们发现这是一个回文串，“bcdcb”也是回文串，“cdc”也是回文串，“d”也是一个回文串，我们可以发现一个规律：回文串去掉一个头和一个尾也是一个回文串

这样我们可以用动态规划的方法来解决这个问题

F(i,j)表示字符串s的第i到第j个字符组成的串，F(i,j)=true表示是回文串，F(i,j)=false表示不是回文串
从上面解释可以知道若F(i+1,j-1)为回文串，并且满足字符串s的第i和第j个字符相等，那么F(i,j)才会是回文串

因此我们可以写出动态规划的状态转移方程：F(i,j) = F(i+1,j-1) && (Si==Sj)，此方程表示的意思是：F(i+1,j-1)为回文串并且s的第i个字符和第j个字符相等F(i,j)才是回文串

代码实现

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxLen = 1; //回文子串的最大长度
        int begin = 0; //回文子串的起始位置
        if(len < 2){ //如果字符串只有一个元素，那么肯定是回文串
            return s;
        }
        //dp[i][j]表示s的第i个到第j个字符是否是回文串
        boolean[][] dp = new boolean[len][len]; 
        for(int i = 0;i < len;i++){ //长度为1的子串是回文串
            dp[i][i] = true;
        }
        char[] arr = s.toCharArray();
        for(int L = 2;L <= len;L++){  //L为子串的长度
            for(int i = 0;i < len;i++){ //i为子串的最左下标
                int j = L + i - 1; //j为子串的最右下标
                if(j >= len){ //下标越界，退出循环
                    break;
                }
                if(arr[i] != arr[j]){ //子串的首尾字符不相等，肯定不是回文串
                    dp[i][j] = false;
                }else {
                    //子串首位元素相等时
                    if(j - i < 3){  //如果子串长度为2，3时，就是回文串
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1]; //若dp[i+1][j-1]为回文串则就是回文串
                    }
                }
                if(dp[i][j] && j-i+1>maxLen){ //更新最大回文子串的长度和子串的起始位置
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen); //从s中截取最大的回文子串返回
    }
}

代码解析

 

复杂度分析

时间复杂度：外部循环子串长度，内部循环子串的起始值，双层循环嵌套，时间复杂度为O(n^2) 

空间复杂度：存储动态规划所需要的空间dp[len][len]，故空间复杂度为O(n^2)