5. 最长回文子串
2022-04-14 本文已影响0人
邦_
我的思路是。。 左边固定 右边移动寻找对应的子串 然后判断 修改最大长度和开始位置
但是时间复杂度上有点高
func longestPalindrome(_ s: String) -> String {
if s.count == 1 {
return s
}
var right = 0
var len = 0
let array = Array(s)
let m = array.count
var start = 0
for i in 0..<m {
right = i
while right < m {
if valid(array,i,right) {
if right - i >= len {
start = i
len = right - i + 1
}
}
right += 1
}
}
let str = s as NSString
return str.substring(with: NSMakeRange(start, len))
}
func valid(_ array:Array<Character> ,_ left :Int,_ right:Int) -> Bool{
if right == left {
return true
}
var start = left
var end = right
while start < end {
if array[start] != array[end] {
return false
}else {
start += 1
end -= 1
}
}
return true
}
优化的解法，利用回文子串的对称性
中心扩散法 从中间往两边移动指针
func longestPalindrome(_ s: String) -> String {
if s.count < 2 {
return s
}
let array = Array(s)
let m = array.count
var start = 0
var end = 0
for i in 0..<m {
let len1 = expand(array, i, i)
let len2 = expand(array, i, i + 1)
let len = max(len1, len2)
if len > end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
let str = s as NSString
return str.substring(with: NSMakeRange(start, end - start + 1))
}
func expand(_ array: Array<Character>,_ left: Int ,_ right: Int) -> Int {
//如果left == right 说明是奇数 对称点在中间
let len = array.count
var start = left
var end = right
while start >= 0 && end < len {
if array[start] == array[end] {
start -= 1
end += 1
}
else {
break
}
}
return end - start - 1
}
截屏2022-04-13 下午5.18.18.png
动态规划的解法
func longestPalindrome(_ s: String) -> String {
let strArray = Array(s)
let length = strArray.count
//开始构建dp数组
let temp = Array.init(repeating: -1, count: length)
var dp = Array.init(repeating: temp, count: length)
//用来记录开始位置和长度
var startIndex = 0
var maxLength = 0
for i in (0..<length).reversed() {
for j in (i..<length).reversed() {
//如果长度小于等于2的话,只需要判断i，j是否相等
if j - i <= 1 {
if strArray[i] == strArray[j] {
dp[i][j] = 1
//记录开始位置和长度
if maxLength < (j - i + 1) {
maxLength = j - i + 1
startIndex = i
}
}else {
dp[i][j] = 0
}
}
//大于2的话
else {
//先判断两端的是否相等，在判断内部的是否是回文子串
if strArray[i] == strArray[j] {
dp[i][j] = dp[i + 1][j - 1]
//记录开始位置和长度
if dp[i][j] == 1 {
//记录开始位置和长度
if maxLength < (j - i + 1) {
maxLength = j - i + 1
startIndex = i
}
}
}//两端都不想等的话，不用判断内部了
else {
dp[i][j] = 0
}
}
}
}
let tempStr = NSString(string: s)
return tempStr.substring(with: NSMakeRange(startIndex, maxLength))
}
