三、最长回文子串

暴力解法

• 时间复杂度 O(n^3)
• 空间复杂度O(1)
• 三重遍历：外层、内层、反向判断字符串是否回文串

// 1.最长回文子串
    func longestPalindrome(_ s: String) -> String {
        //
        /**
         桶集合：不同的字符对应不同的桶
         key：字符
         value：前一个字符下标
         */
        var buckets:[Character:[Int]] = Dictionary()
        if(s.count == 0 || s.count == 1){
            return s
        }
        // 初始化
        var result = s.prefix(1)
        for i in 0...s.count-1 {
            let index = s.index(s.startIndex, offsetBy: i)
            let character = s[index]
            if let previousIndexs = buckets[character] {
                for previousIndex in previousIndexs {
                    // 如果有这个字符的桶，那么截取字符串
                    let start = s.index(s.startIndex, offsetBy: previousIndex)
                    let end = s.index(s.endIndex, offsetBy: -(s.count-i))
                    let middle = s[start...end]
                    if(middle.count > 0){
                        if(middle == String(middle.reversed())){
                            // 回文字符串，如果middle比较长，更新最长回文字符串
                            if(middle.count > result.count){
                                result = middle
                            }
                        }
                    }
                }
                buckets[character]!.append(i)
            }else {
                buckets[character] = [i]
            }
        }
        return String(result)
    }

中心扩散

• 时间复杂度O(n^2)
• 空间复杂度O(1)
• 与暴力解法不同，因为能扩散的即回文，不需要反向遍历
• 利用了回文轴对称的特点
• 遍历下标为 i 时，考虑双中心的情况，i、i-i+1
• i，j中间的才是回文串，不包括 i、j

动态规划

• dp[i,j] 是否是回文，只需要满足两个条件，S(i)=S(j) && dp[i+1,j-1]也是回文。
• 时间复杂度O(n^2)
• 空间复杂度O(n^2)

不具备实用性、但是Manacher算法的基础

// 1.最长回文子串
func longestPalindrome(_ s: String) -> String {
    if s.count == 0 {
        return ""
    }else if s.count == 1 {
        return s
    }
    /*
     动态规划：
     字典，key = (i,j) value = isPalindrome
     i,j为字符串对应的下标
     从少到多，判断是否是回文的dp方程
     dp[i,j]
     si = sj
     dp[i+1,j-1] = isPalindrome = true
     */
    var dp :[Combination:Bool] = [:]
    var maxLength = 1
    var maxCombination:Combination = Combination[0,0]
    for i in 0...s.count {
        // dp[i,i] = true
        dp.updateValue(true, forKey: Combination[i,i])
    }
    
    for lenth in 2...s.count {
        for i in 0...s.count - lenth {
            let dpi = i
            let dpj = i + lenth - 1
            if dpj == dpi + 1 && s[dpi] == s[dpj] {
                dp.updateValue(true, forKey: Combination[dpi,dpj])
                if(lenth > maxLength){
                    maxLength = lenth
                    maxCombination = Combination[dpi,dpj]
                }
            }else if s[dpi] == s[dpj] && dp[Combination[dpi+1,dpj-1]] == true {
                dp.updateValue(true, forKey: Combination[dpi,dpj])
                if(lenth > maxLength){
                    maxLength = lenth
                    maxCombination = Combination[dpi,dpj]
                }
            }else {
                dp.updateValue(false, forKey: Combination[dpi,dpj])
            }
            
        }
    }
    
    let startIndex = s.index(s.startIndex, offsetBy: maxCombination.i)
    let endIndex = s.index(startIndex, offsetBy: maxLength)
    let res = String(s[startIndex..<endIndex])
    
    return res
}

struct Combination : Hashable {
    var i = 0
    var j = 0
    
    // 实现 hashValue 属性
    var hashValue: Int {
        // 使用 Cantor pairing function 计算哈希值
        return ((i + j) * (i + j + 1) / 2) + j
    }

    func hash(into hasher: inout Hasher) {
        
    }
    
    // 实现 == 操作符
    static func ==(lhs: Combination, rhs: Combination) -> Bool {
        return lhs.i == rhs.i && lhs.j == rhs.j
    }
    
    static subscript (i:Int,j:Int)->Combination {
        let com = Combination.init(i: i,j: j)
        return com
    }
}

extension String {
    subscript(index:Int)->String{
        let startIndex = self.index(self.startIndex, offsetBy: index)
        let endIndex = self.index(startIndex, offsetBy: 1)
        let res = String(self[startIndex..<endIndex])
        return res
    }
}

Manacher 算法

• 时间复杂度 O(n)
• 原始字符串预处理，动态规划，中心扩散。
• 预处理字符串映射到原始字符串中，原始字符串长度 = (预处理字符串长度 - 1) / 2
• 中心交换公式：mirror = 2 * center - i