一、题目原型:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
二、题目意思剖析:
回文其实是对称的一个字符串。
比如:aba 、xyx、 mnnm、xoox 这样子。。。
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
输入: "cbbd"
输出: "bb"
三、解题思路:
中心法
官方解释:
事实上,只需使用恒定的空间,我们就可以在 O(n^2) 的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 2n−1 个这样的中心。
你可能会问,为什么会是 2n−1 个,而不是 n 个中心?原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba” 的中心在两个 ‘b’ 之间)。
我的理解:
我们根据对称的这个特性,来进行查找,以一个点为中心,两个指针左右移动,如果两边对应的字母相同,那么就继续移动,直到超出边界或者两边字母不同。
// 返回当前回文最大的长度
func haha(_ letters: [String],_ left: Int, _ right: Int) -> (Int) {
var L:Int = left
var R: Int = right
// 当左边指针不小于0,当右边指针不超过字符串长度
// 并且左右两个数值要相等
while L>=0 && R<letters.count && letters[L] == letters[R] {
L = L - 1
R = R + 1
}
return R - L - 1
}
func longestPalindrome(_ s: String) -> String {
var letters: [String] = []
for char in s {
let str: String = String.init(char)
letters.append(str)
}
var start:Int = 0
var end: Int = 0
var huiwen: String = ""
for i in 0..<letters.count {
// 这分为两种情况:1.回文长度为奇数时,中心在中间那个字母
// 2.回文长度为偶数时,中心在两个字母之间
let len1: Int = haha(letters, i, i)
let len2: Int = haha(letters, i, i+1)
// 取最大值
let len: Int = len1 > len2 ? len1 : len2
if len > end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
for i in start..<end+1 {
huiwen.append(letters[i])
}
return huiwen
}
四、小结
一切一切的算法,前提是要找到规律。然后一步一步剖析找出最好的算法。
在本题中,我的笔记思路只画出了一种情况,还有另一种情况就是回文长度为偶数时,中心在两个字母之间,也是一样的规律去找。最后比较这两种情况,找出最大值就行了。
有其他好的方法请极速留言,非常乐意一起探讨。😄
网友评论