题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。回文是一个正读和反读都相同的字符串，例如，“aba” 是回文，而“abc” 不是。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
思路
1、暴力求解
最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。求每一个子串时间复杂度O(N2)，判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N3)。
func isPalindromic(_ s: String) -> Bool {
let array = Array(s)
let length = array.count
for i in 0..<length / 2 {
if array[i] != array[length - i - 1] { // 首尾比较
return false
}
}
return true
}
func longesPalindrome(_ s: String) -> String {
var maxString = ""
if s.count < 2 { return s }
let length = s.count
for i in 0..<length {
for j in i+1...length {
let startIndex = s.index(s.startIndex, offsetBy: i)
let endIndex = s.index(s.startIndex, offsetBy: j)
let subString = String(s[startIndex..<endIndex])
if isPalindromic(subString) && subString.count > maxString.count {
maxString = subString
}
}
}
return maxString
}
添加String扩展简单截取子串
extension String {
subscript(_ range: CountableRange<Int>) -> String {
let start = index(startIndex, offsetBy: max(0, range.lowerBound))
let end = index(start, offsetBy: min(self.count - range.lowerBound,
range.upperBound - range.lowerBound))
return String(self[start..<end])
}
}
func longesPalindrome(_ s: String) -> String {
var maxString = ""
if s.count < 2 { return s }
let length = s.count
for i in 0..<length {
for j in i+1...length {
let subString = s[i..<j]
if isPalindromic(subString) && subString.count > maxString.count {
maxString = subString
}
}
}
return maxString
}
2、中心扩展
中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法时间复杂度为O(N2)。
具体实现
1、通过遍历，取到第一个字符，设该字符为回文串的中心字符
2、回文串有两种，一种是(abba)，一种是(abcba)，也就是单数或双数两种
3、同时还有相同字符的回文串，例如(aaa)，(bbbb)
4、所以，在遍历一开始，设置start与end为 i，设默认情况为单数回文串
5、然后通过 while 循环，分别对 start 进行左移 ，对 end 进行右移， 判断是否为双数回文串
6、再通过 while 对回文串同时进行 start -= 1 与 end += 1
7、如果获取到的 start -= 1 的字符 与 end += 1 的字符相同， 则扩大回文串。否则退出循环
8、当所有遍历循环结束时， dic字典中，存放着回文串的长度，start与end
9、通过start，end拼接出完整字符串，并return
// 172ms
func longestPalindrome(_ s: String) -> String {
var start = 0
var end = 0
let stringArray = Array(s)
var i = 0
var dic = [String : Int]()
for element in stringArray {
start = i
end = i
while start - 1 >= 0 { // 左移多位判断
if stringArray[start - 1] == element {
start -= 1
} else {
break
}
}
while end + 1 <= (stringArray.count - 1) { // 右移多位判断
if stringArray[end + 1] == element {
end += 1
} else {
break
}
}
while start >= 0 && end <= (stringArray.count - 1) { // 判断是否为回文串
if start != end {
if stringArray[start] == stringArray[end] { // 子字符
if dic["count"] ?? 0 < (end - start + 1) { // 存储位置信息
dic["count"] = end - start + 1
dic["start"] = start
dic["end"] = end
}
} else {
break
}
}
//保存起来目前最大的回文串之后继续往外扫
start -= 1
end += 1
}
i += 1 // 偏移中心比对点
}
var newStr: [String] = []
start = dic["start"] ?? 0
end = dic["end"] ?? 0
for index in start ... end {
newStr.append(stringArray[index].description)
}
return newStr.joined() //去掉空格
}
更快速的中心扩散
// 120 ms
func longestPalindrome(_ s: String) -> String {
let array = Array(s)
let length = array.count
if length < 2 { // 直接返回
return s
}
var maxLength = 1
var begin = 0
for index in 0..<length-1 {
let oddLength = centerLength(array, index, index) // 偶数长度
let evenLength = centerLength(array, index, index+1) //奇数长度
let oeMax = max(oddLength, evenLength) // 最大回文长度
if oeMax > maxLength { // 更新最大值
maxLength = oeMax
begin = index - (maxLength-1)/2
}
}
// 截取子串
return String(array[begin..<begin+maxLength])
}
func centerLength(_ s: [String.Element], _ left: Int, _ right: Int) -> Int {
let length = s.count
var i = left, j = right
while i>=0 && j < length { // 左边大于等于0，右边小于整个字符串的长度
if s[i] == s[j] { // 如果左右两边值相等
i -= 1 // 向外扩散，左边继续往左边移动
j += 1 // 右边继续往右边移动
} else {
break
}
}
// 返回回文的长度
return j-i-1;
}
3、动态规划
回文字符串的子串也是回文，因此用dp[i,j]（表示以i开始以j结束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O(N2)，算法复杂度也是O(N2)。
// 2036ms
func longestPalindrome1(_ s: String) -> String {
if s.count <= 1 { return s }
let s = Array(s)
// 最长回文串的起始位置 和长度
var maxLen = 1
var begin = 0
// 二维数组
var dp = [[Bool]](repeating: [Bool](repeating: false, count: s.count), count: s.count)
for i in (0..<s.count).reversed() {
for j in i..<s.count {
let len = (j-i+1)
dp[i][j] = (s[i] == s[j]) && ( len <= 2 || dp[i+1][j-1])
if dp[i][j] && len > maxLen { // 更新最大值
maxLen = len
begin = i
}
}
}
return String(s[begin..<begin+maxLen])
}
网友评论