当前位置：首页 > article >正文

【Swift 算法实战】利用 KMP 算法高效求解最短回文串

article 2025/2/25 12:50:16

在这里插入图片描述

网罗开发 （小红书、快手、视频号同名）

大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

文章目录

- 摘要
- 描述
- 题解答案
- - KMP 最长前缀匹配
- 题解代码分析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
- 未来展望
- 参考资料

摘要

在字符串处理问题中，构造最短回文串是一种常见的面试考察点。本篇文章将探讨如何在字符串前面添加最少的字符，使其成为回文串。我们将使用 KMP（Knuth-Morris-Pratt）部分匹配表 来优化搜索过程，使其时间复杂度达到 O(n)。最后，我们通过示例代码进行测试，并分析其时间和空间复杂度。

描述

给定一个字符串 s，可以在字符串前面添加字符，使其转换为 最短回文串，并返回最终结果。例如：

示例 1：

输入: "aacecaaa"
输出: "aaacecaaa"

示例 2：
```
输入: "abcd"
输出: "dcbabcd"
```

约束条件：

0 <= s.length <= 5 * 10^4
s 仅包含小写英文字母。

题解答案

KMP 最长前缀匹配

思路：

构造辅助字符串：我们将 s 反转，并构造 newStr = s + "#" + reversed(s)。
构造 LPS（最长前缀后缀匹配）数组：
- LPS 数组的最后一个元素代表 s 本身已经是回文的最大部分，其余部分需要添加到 s 前面。
生成结果：
- 计算 prefixToAdd = rev.prefix(s.count - LPS.last!)
- 返回 prefixToAdd + s

题解代码分析

import Foundation

class Solution {
    func shortestPalindrome(_ s: String) -> String {
        if s.isEmpty { return s }

        let rev = String(s.reversed())
        let newStr = s + "#" + rev
        let lps = computeLPS(newStr)
        let prefixToAdd = rev.prefix(s.count - lps.last!)

        return prefixToAdd + s
    }

    private func computeLPS(_ s: String) -> [Int] {
        let chars = Array(s)
        let n = chars.count
        var lps = [Int](repeating: 0, count: n)
        var length = 0
        var i = 1

        while i < n {
            if chars[i] == chars[length] {
                length += 1
                lps[i] = length
                i += 1
            } else {
                if length > 0 {
                    length = lps[length - 1]
                } else {
                    lps[i] = 0
                    i += 1
                }
            }
        }

        return lps
    }
}

代码解读：

computeLPS()：
- 构建 KMP 的 最长前缀后缀匹配表 (LPS)。
- lps[i] 表示 s[0...i] 子串的最长前缀后缀匹配长度。
- 通过 while 遍历整个字符串，维护 前缀长度 变量 length，高效计算 LPS 数组。
shortestPalindrome()：
- 计算 s + "#" + reversed(s) 的 LPS。
- 计算需要添加的前缀 prefixToAdd，拼接后返回最终结果。

示例测试及结果

let solution = Solution()
print(solution.shortestPalindrome("aacecaaa")) // 输出: "aaacecaaa"
print(solution.shortestPalindrome("abcd"))    // 输出: "dcbabcd"
print(solution.shortestPalindrome("race"))    // 输出: "ecarace"
print(solution.shortestPalindrome("a"))       // 输出: "a"
print(solution.shortestPalindrome(""))        // 输出: ""