【leetcode】5.最长回文子串js

题目代码-中心扩散法好这题还是看题解了。思路是采用中心扩散法遍历到一个字符就以它为中心向两边扩散看最长的回文子串长度多少如果比现有的长就更新当前最长的回文子串没有就继续往下遍历。需要注意的点是回文子串可能是奇数长度和偶数长度两种情况。/** * param {string} s * return {string} */ var longestPalindrome function(s) { if (s.length 2) return s let res for (let i 0; i s.length; i) { // 回文字串长度是奇数 helper(i, i) // 回文字串长度是偶数 helper(i, i1) } function helper(left, right) { while (left 0 right s.length s[left] s[right]) { left-- right } // 这里用right - left - 1是因为循环之后left和right恰好是不满足条件的时刻 // 因此两个边界不能取应该取left 1到right - 1这个区间 if (right - left - 1 res.length) { // slice左闭右开取[left 1, right - 1] res s.slice(left 1, right) } } return res };时间复杂度是O(n²)空间复杂度是O(1)代码-动态规划原题解在这里传送门特别厉害啊我膜拜1. 定义dp数组用一个二维数组dp[i][j]来表示字符串中下标从i到j的子串s[i...j]是不是回文子串2. 状态转移规则当 s[i] ! s[j]显然 s[i..j] 不是回文串当 s[i] s[j] 时若 j - i 3子串长度为2或3只要两端字符相等就是回文串否则要看内部子串 dp[i 1][j - 1] 是否为回文。3. 状态初始化所有dp[i][i]都是true因为只有单个字符肯定是回文。4. 最终目标在遍历过程中记录最长回文的起始下标 begin 和长度 maxLen最终用 s.substring(begin, begin maxLen) 返回。这里就直接贴佬的代码了可供学习参考。/** * param {string} s * return {string} */ var longestPalindrome function(s) { const len s.length; if (len 2) return s; // 长度小于2直接返回原串 let maxLen 1; // 初始化最大长度 let begin 0; // 初始化起始位置 const dp Array.from({ length: len }, () Array(len).fill(false)); // 所有长度为1的子串都是回文串 for (let i 0; i len; i) { dp[i][i] true; } const charArray s.split(); // 枚举子串结束位置 j for (let j 1; j len; j) { // 枚举子串起始位置 i必须 i j for (let i 0; i j; i) { if (charArray[i] ! charArray[j]) { dp[i][j] false; } else { if (j - i 3) { dp[i][j] true; // 长度为2或3只要两端相等就是回文 } else { dp[i][j] 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); };时间复杂度和空间复杂度都是O(n²)