题目描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
分析
回文就是类似于"奶牛牛奶", "狗咬人咬狗"这种， 从中间向两边对称的字符串。
最简单的方式暴力遍历，，假设有字符串 "babad"， 要遍历其中每一个子串， 需要两层循环， O(n ^ 2)的时间复杂度。 对每一个子串，要判断是否是回文， 又要一层循环，因此暴力遍历的方法在这道题的时间复杂度是0(n)
针对暴力遍历的优化， 就是减少一些冗余的遍历， 例如 如果在某个位置 i， 左右两侧的字符相同， 则 i - 1 —— i + 1之间的字符串就是一个回文， 此时再向两边扩散， 如果两侧字符不相同了， 就可以停止对位置 i 的检查了， 因为之后的肯定都不是回文， 这个法子叫"中心扩散法"
用了这个法子， 我们只需要用一个指针 i 对字符串遍历一次, 对每一个位置 i， 再使用两个指针left, right分别指向 i 的两侧，检查两侧的字符是否相同， 如果相同， 计算长度的最大值，接着从中心扩散检查left - 1 和 right + 1的值是否相同，， 直到 left - n 和 right + n不同时， 移动 i 指针检查下一个位置。
还要注意点的就是， 有"aba"和"abba"这两种形式的回文，因此要分开检查
Javascript
/**
* @param {string} s
* @return {string}
*/
// 中心扩散 O(n ^ 2)
var longestPalindrome = function(s) {
// 边界情况提前过滤
if (s.length < 2) {
return s
}
// 需要返回的最长回文子串
let result = ''
// 当前位置的最大回文长度
let max = 0
// 检查left到start范围是否有回文的方法
let check = function(s, left, right) {
while(left >= 0 && right < s.length) {
if (s[left] === s[right]) {
if (right - left + 1 > max) {
max = right - left + 1
result = s.substring(left, right + 1)
}
left--
right++
} else {
return
}
}
}
// 检查字符串中每一个位置
for(let i = 0; i< s.length; i++) {
// 检查"aba"式的回文
check(s, i, i)
// 检查"abba"式的回文
check(s, i, i + 1)
}
return result
};
运行结果
事实上， 最长回文的最好解法是马拉车算法(Manacher's Algorithm), 这个算法是专门解决字符串最长回文的线性算法， 时间复杂度可以降到O(n)， 这里是一个马拉车的动画
http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/
You have been upvoted by all four members of the @steemexplorers team. Steemexplorers is an initiative to help bring all Steemians information on various services and communities operating all on the STEEM blockchain in a centralized location to save you time and help you grow here on Steemit. It's free, it's easy, and there's a whole lot of information here that you can put to good use. Please come by our discord channel to learn more and feel free to ask as many questions as you'd like. We're here to help! Link to Discord: https://discord.gg/6QrMCFq
Congratulations @hughie8! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPTo support your work, I also upvoted your post!
Vote for @Steemitboard as a witness to get one more award and increased upvotes!
This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.
You got voted by @curationkiwi thanks to hughie8! This bot is managed by KiwiJuce3 and run by Rishi556, you can check both of them out there. To receive upvotes on your own posts, you need to join the Kiwi Co. Discord and go to the room named #CurationKiwi. Submit your post there using the command "!upvote (post link)" to receive upvotes on your post. CurationKiwi is currently supported by donations from users like you, so feel free to leave an upvote on our posts or comments to support us!
We have also recently added a new whitelist feature for those who would like to support CurationKiwi even more! If you would like to receive upvotes more than 2x greater than the normal upvote, all you need to do is delegate 50 SP to @CurationKiwi using this link.
You got a 32.79% upvote from @whalepromobot courtesy of @hughie8!