Open liangbus opened 4 years ago
题目:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
拿到题目,不着急写代码,这里当然可以通过暴力方法去解(把所有子串枚举出来,然后检查是否为回文串,一一比较),但是这并是个好方法,这里我想说的是另外一个比较容易想到的方法:中心扩展算法,接下来先一步步分析:
按上上面的分析,基本能够解决这道题了,详细的代码(.ts)
const longestPalindrome = function(s: string): string { let max = s.charAt(0); let i = 1, len = s.length let left = -1, right = -1; if(!s || len <= 1) return s; let prev = '', cur = '', next = ''; // 单点为对称中心,如: cqbgbdfg -> bgb while(i < len && max.length < ((len - 1 - i) * 2 + 1)) { prev = s.charAt(i - 1); cur = s.charAt(i); next = s.charAt(i + 1) if(prev === next) { let tmpMax = (prev + cur + next) left = i - 2; right = i + 2; while (left >= 0 && right < len && s.charAt(left) === s.charAt(right)) { tmpMax = s.charAt(left) + tmpMax + s.charAt(right) left-- right++ } if(tmpMax.length > max.length) { max = tmpMax } } i++ } if(max.length === s.length) return max // 双字符为对称中心, 如: ccabbaad -> abba i = 1 while(i < len && max.length <= ((len - 1 - i) * 2) + 2) { prev = s.charAt(i - 1); cur = s.charAt(i); if(cur === prev) { let tmpMax = cur + prev left = i - 2; right = i + 1; while (left >= 0 && right < len && s.charAt(left) === s.charAt(right)) { tmpMax = s.charAt(left) + tmpMax + s.charAt(right) left-- right++ } if(tmpMax.length > max.length) { max = tmpMax } } i++ } return max };
执行时间上,有时候能够上110+ms,有时是160+ms,总之还并不是最优的,看到网友们不少是在100以内的,更优的代码,就自己解题后去看吧,这里就不贴了
题目:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例:
拿到题目,不着急写代码,这里当然可以通过暴力方法去解(把所有子串枚举出来,然后检查是否为回文串,一一比较),但是这并是个好方法,这里我想说的是另外一个比较容易想到的方法:中心扩展算法,接下来先一步步分析:
按上上面的分析,基本能够解决这道题了,详细的代码(.ts)
执行时间上,有时候能够上110+ms,有时是160+ms,总之还并不是最优的,看到网友们不少是在100以内的,更优的代码,就自己解题后去看吧,这里就不贴了