We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
题目:给定一个字符串 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以内的,更优的代码,就自己解题后去看吧,这里就不贴了
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例:
拿到题目,不着急写代码,这里当然可以通过暴力方法去解(把所有子串枚举出来,然后检查是否为回文串,一一比较),但是这并是个好方法,这里我想说的是另外一个比较容易想到的方法:中心扩展算法,接下来先一步步分析:
按上上面的分析,基本能够解决这道题了,详细的代码(.ts)
执行时间上,有时候能够上110+ms,有时是160+ms,总之还并不是最优的,看到网友们不少是在100以内的,更优的代码,就自己解题后去看吧,这里就不贴了
The text was updated successfully, but these errors were encountered: