[最長(zhǎng)回文子串]
解題思路一：我們所需的時(shí)間復(fù)雜度是O(N)
用一個(gè)字典保存一個(gè)字符串出現(xiàn)的第一次index冬竟，然后遍歷字符串直到結(jié)束笔刹。
代碼如下：
class Solution {
func longestPalindrome(_ s: String) -> String {
var dic = [Character : Int]()
var maxLength = 0
var currentChar: Character?
var index = 0
s.forEach { (char) in
if let startIndex = dic[char]{
let length = index + 1 - startIndex
if length > maxLength {
currentChar = char
maxLength = length
}
}else{
dic[char] = index
}
index += 1
}
if maxLength == 0{
if s.length > 1{
return String(s[s.index(s.endIndex, offsetBy: -1)..<s.endIndex])
}else{
return s
}
}else{
let startIndex = dic[currentChar!]
let sIndex = s.index(s.startIndex, offsetBy: startIndex!)
let eIndex = s.index(sIndex, offsetBy:maxLength)
return String(s[sIndex..<eIndex])
}
}
}
第二種解法：
采用快速遍歷：
一個(gè)從頭開始計(jì)算一個(gè)從尾部開始拷获。
