【LeetCode】5-最长回文子串

欢迎来到李耶的频道【LeetCode面试题】。最长回文子串题目给你一个字符串s找到s中最长的回文子串。输入s babad 输出bab 解释aba 也是一个有效答案输入s cbbd 输出bb解法一中心扩展法思路回文串的中心可以是一个字符奇数长度或两个字符偶数长度。遍历每个可能的中心向两端扩展记录最长的回文子串。functionlongestPalindrome(s){if(!s||s.length2)returns;letstart0;letmaxLen1;functionexpandAroundCenter(left,right){while(left0rights.lengths[left]s[right]){constcurLenright-left1;if(curLenmaxLen){maxLencurLen;startleft;}left--;right;}}for(leti0;is.length;i){expandAroundCenter(i,i);// 奇数长度如 abaexpandAroundCenter(i,i1);// 偶数长度如 abba}returns.substring(start,startmaxLen);}时间复杂度 / 空间复杂度O(n²) / O(1)优势实现简单空间效率高是面试中最推荐的手写解法解法二动态规划思路用dp[i][j]表示子串s[i..j]是否为回文串。状态转移dp[i][j] (s[i] s[j] dp[i1][j-1])从短子串向长子串递推。functionlongestPalindrome(s){if(!s||s.length2)returns;constns.length;constdpArray.from({length:n},()Array(n).fill(false));letstart0;letmaxLen1;// 所有长度为 1 的子串都是回文for(leti0;in;i){dp[i][i]true;}// 按长度枚举for(letlen2;lenn;len){for(leti0;in-len;i){constjilen-1;if(s[i]s[j]){if(len2||dp[i1][j-1]){dp[i][j]true;if(lenmaxLen){maxLenlen;starti;}}}}}returns.substring(start,startmaxLen);}时间复杂度 / 空间复杂度O(n²) / O(n²)优势思路清晰易于理解递推关系适合初学者劣势空间复杂度较高大字符串下不优解法对比解法时间 / 空间复杂度优势推荐指数中心扩展法O(n²) / O(1)空间最优实现简单⭐⭐⭐⭐⭐动态规划O(n²) / O(n²)思想经典易于理解⭐⭐⭐扩展题最长回文子序列给定一个字符串s找到其中最长的回文子序列并返回该序列的长度。子序列不要求连续回文子串给定一个字符串统计其中回文子串的数量。最短回文串给定一个字符串s通过在前面添加字符将其转换为回文串返回最短的回文串。“大道至简实干为要。” —— 《荀子》关注李耶每天一道面试题一起卷起来