🍊题目
题目链接：最长回文子串
给一个字符串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)
