每日算法 -【Swift 算法】寻找字符串中最长回文子串(三种经典解法全解析)

🧩 最长回文子串问题：三种经典解法全解析（含代码注释）

本文将系统讲解“最长回文子串”问题的三种常见解法：中心扩展法、动态规划、马拉车算法（Manacher’s Algorithm），并进行对比与总结。

📌 问题描述

给定一个字符串 s，返回其中 最长的回文子串。

示例：

• 输入："babad"
• 输出："bab" 或 "aba"

✅ 解法一：中心扩展法（Expand Around Center）

🧠 思路

• 回文的本质是“对称”
• 遍历每个字符，尝试以它为中心向两边扩展，总共需要考虑 2n - 1 个中心（包括字符与字符之间的间隙）。
• 需要对奇数长度（如 "aba"）和偶数长度（如 "abba"）分别处理

⏱ 复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

🧑‍💻 Swift 实现（含注释）

func longestPalindromeCenter(_ s: String) -> String {
    if s.isEmpty { return "" }

    let chars = Array(s)
    var start = 0, end = 0

    for i in 0..<chars.count {
        let len1 = expand(chars, left: i, right: i) // 奇数长度
        let len2 = expand(chars, left: i, right: i + 1) // 偶数长度
        let len = max(len1, len2)

        if len > end - start {
            start = i - (len - 1) / 2
            end = i + len / 2
        }
    }

    return String(chars[start...end])
}

func expand(_ chars: [Character], left: Int, right: Int) -> Int {
    var L = left, R = right
    while L >= 0 && R < chars.count && chars[L] == chars[R] {
        L -= 1
        R += 1
    }
    return R - L - 1 // 实际回文长度
}

✅ 解法二：动态规划（Dynamic Programming）

🧠 思路

• 定义 dp[i][j] 表示 s[i...j] 是否为回文串。
• 转移方程：
  • dp[i][j] = true if s[i] == s[j] && dp[i+1][j-1]

⏱ 复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)

🧑‍💻 Swift 实现（含注释）

func longestPalindromeDP(_ s: String) -> String {
    let chars = Array(s)
    let n = chars.count
    if n < 2 { return s }

    var dp = Array(repeating: Array(repeating: false, count: n), count: n)
    var maxLen = 1
    var start = 0

    for i in 0..<n {
        dp[i][i] = true
    }

    for length in 2...n {
        for i in 0...(n - length) {
            let j = i + length - 1
            if chars[i] == chars[j] {
                if length == 2 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }

                if dp[i][j] && length > maxLen {
                    maxLen = length
                    start = i
                }
            }
        }
    }

    return String(chars[start..<start + maxLen])
}

✅ 解法三：马拉车算法（Manacher’s Algorithm）

🧠 思路

• 首先对字符串预处理，使得所有回文都是奇数长度（例如："abba" → "#a#b#b#a#"）
• 使用数组 p[i] 记录以第 i 个字符为中心的最大回文“半径”
• 利用已知的对称中心和边界进行跳跃扩展，从而实现线性时间复杂度

⏱ 复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

🧑‍💻 Swift 实现（含注释）

func longestPalindromeManacher(_ s: String) -> String {
    // Step 1: 预处理字符串，在每个字符中间加入 #
    let t = Array("#" + s.map { "\($0)#" }.joined())
    let n = t.count
    var p = Array(repeating: 0, count: n)

    var center = 0, right = 0
    var maxLen = 0, maxCenter = 0

    for i in 0..<n {
        let mirror = 2 * center - i // i 关于 center 的对称点

        // Step 2: 利用镜像对称性快速扩展
        if i < right {
            p[i] = min(right - i, p[mirror])
        }

        // Step 3: 尝试向左右扩展
        var a = i + p[i] + 1
        var b = i - p[i] - 1
        while a < n && b >= 0 && t[a] == t[b] {
            p[i] += 1
            a += 1
            b -= 1
        }

        // Step 4: 更新 center 和 right
        if i + p[i] > right {
            center = i
            right = i + p[i]
        }

        // Step 5: 更新最大值
        if p[i] > maxLen {
            maxLen = p[i]
            maxCenter = i
        }
    }

    // Step 6: 从原始字符串中提取结果
    let start = (maxCenter - maxLen) / 2
    let end = start + maxLen
    return String(s[s.index(s.startIndex, offsetBy: start)..<s.index(s.startIndex, offsetBy: end)])
}

🧪 示例输出

print(longestPalindromeCenter("babad"))   // 输出: "bab" 或 "aba"
print(longestPalindromeManacher("cbbd"))  // 输出: "bb"
print(longestPalindromeDP("babad"))  // "bab" 或 "aba"

📊 三种方法对比总结

✅ 最佳实践推荐