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

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

news 来源：原创 2025/7/5 22:28:51

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

本文将系统讲解“最长回文子串”问题的三种常见解法：中心扩展法、动态规划、马拉车算法（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 = 0for 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) / 2end = i + len / 2}}return String(chars[start...end])
}func expand(_ chars: [Character], left: Int, right: Int) -> Int {var L = left, R = rightwhile L >= 0 && R < chars.count && chars[L] == chars[R] {L -= 1R += 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.countif n < 2 { return s }var dp = Array(repeating: Array(repeating: false, count: n), count: n)var maxLen = 1var start = 0for i in 0..<n {dp[i][i] = true}for length in 2...n {for i in 0...(n - length) {let j = i + length - 1if 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 = lengthstart = 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.countvar p = Array(repeating: 0, count: n)var center = 0, right = 0var maxLen = 0, maxCenter = 0for 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] + 1var b = i - p[i] - 1while a < n && b >= 0 && t[a] == t[b] {p[i] += 1a += 1b -= 1}// Step 4: 更新 center 和 rightif i + p[i] > right {center = iright = i + p[i]}// Step 5: 更新最大值if p[i] > maxLen {maxLen = p[i]maxCenter = i}}// Step 6: 从原始字符串中提取结果let start = (maxCenter - maxLen) / 2let end = start + maxLenreturn 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"

📊 三种方法对比总结

算法	时间复杂度	空间复杂度	实现难度	适用场景
中心扩展法	O(n²)	O(1)	⭐⭐ 易	面试首选，简洁实用
动态规划	O(n²)	O(n²)	⭐⭐⭐ 中等	适用于变种题型
马拉车算法	O(n)	O(n)	⭐⭐⭐⭐ 高	性能关键、竞赛场景

✅ 最佳实践推荐

需求	推荐方法
面试、日常开发、可读性	✅ 中心扩展法
遇到类似子串变种问题	✅ 动态规划
超大数据量、刷算法题、竞赛	✅ 马拉车算法

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

🧩 最长回文子串问题：三种经典解法全解析（含代码注释） 本文将系统讲解“最长回文子串”问题的三种常见解法：中心扩展法、动态规划、马拉车算法（Manacher’s Algorithm），并进行对比与…...

编程日记 2025/7/5 22:28:51

【Java高阶面经：数据库篇】13. MySQL 并发控制秘籍：MVCC 协议与隔离级别深度解析

一、MVCC核心原理：多版本并发控制的基石 1.1 为什么需要MVCC？在传统锁机制中，读写操作会互相阻塞，导致高并发场景下性能下降。MVCC通过多版本数据快照避免读写阻塞，实现：读不加锁：快照读（普通SELECT）不阻塞写操作写不阻塞读：写操作生成新版本，读操作访问历史版本…...

编程日记 2025/6/27 23:10:29

分布式集群中的共识算法及其在时序数据库IoTDB中的应用

一、引言在分布式集群环境中，为了实现海量数据的横向扩展，数据通常被划分为多个子集并分散存储在集群的各个节点上。为了确保数据的高可用性，每个数据子集都会在多个物理节点上存储副本。然而，这种多副本机制也带来了新的挑战&a…...

编程日记 2025/7/5 22:24:24

Java面试实录：从JVM调优到Spring Cloud实践

Java大厂面试：当严肃面试官遇上搞笑程序员场景设定面试官：拥有多年行业经验的技术专家，对Java及相关技术栈有着深入的理解。明哥：一位自认为是“水货”的程序员，擅长用幽默化解紧张气氛，但面对复杂问题…...

编程日记 2025/7/3 3:56:23

自定义协议与序列反序列化

目录引子： 一、再谈 "协议" 二、自定义协议与网络版计算器 1.约定方案一: 2.约定方案二: 3.我们采用的协议三、网络计算器代码 Log.hpp 日志 Makefile Socket.hpp 套接字封装 Protocol.hpp 协议序列化反序列化结构化数据格式规定 TcpSe…...

编程日记 2025/7/5 22:08:14

SAP-ABAP:ABAP异常处理与SAP现代技术融合—— 面向云原生、微服务与低代码场景的创新实践

专题三：ABAP异常处理与SAP现代技术融合 —— 面向云原生、微服务与低代码场景的创新实践一、SAP技术演进与异常处理的挑战随着SAP技术栈向云端、微服务化和低代码方向演进，异常处理面临新场景： Fiori UX敏感度：用户期望前端友…...

编程日记 2025/7/5 22:27:50

JavaScript面试题之消息队列

JavaScript消息队列详解：单线程的异步魔法核心在JavaScript的单线程世界中，消息队列（Message Queue）是实现异步编程的核心机制，它像一位高效的调度员，让代码既能“一心多用”又避免卡顿。本文将深入剖析消…...

编程日记 2025/7/5 21:54:41

【低代码】如何使用明道云调用 Flask 视图函数并传参（POST 方法实践）

在自动化办公或业务流程管理中，明道云提供了强大的 HTTP 请求节点，可以直接调用第三方 API，包括我们常见的 Flask 服务端接口。本文将详细介绍如何使用明道云通过 POST 方法调用 Flask 视图函数并传参，包括配置要点与 Python 后端的参数接收方法。一、场景介绍我们希望…...

编程日记 2025/7/5 16:43:16

广州卓远VR受邀参加2025智能体育典型案例调研活动，并入驻国体华为运动健康联合实验室!

近日，“2025年智能体育典型案例调研活动”在东莞松山湖成功举办。本次调研活动由国家体育总局体育科学研究所和中国信息通信研究院联合主办，旨在深入贯彻中央关于培育新型消费的战略部署，通过激活智能健身产品消费潜力，加快运动健…...

编程日记 2025/7/5 21:57:13

【WebRTC】源码更改麦克风权限

WebRTC源码更改麦克风权限仓库: https://webrtc.googlesource.com/src.git分支: guyl/m125节点: b09c2f83f85ec70614503d16e4c530484eb0ee4f...

编程日记 2025/7/5 21:44:39

spring cloud alibaba-Geteway详解

spring cloud alibaba-Gateway详解 Gateway介绍在 Spring Cloud Alibaba 生态系统中，Gateway 是一个非常重要的组件，用于构建微服务架构中的网关服务。它基于 Spring Cloud Gateway 进行扩展和优化，提供了更强大的功能和更好的性能。 Gat…...

编程日记 2025/7/3 8:42:35

结课作业01. 用户空间 MPU6050 体感鼠标驱动程序

目录一. qt界面实现二. 虚拟设备模拟模拟鼠标实现体感鼠标 2.1 函数声明 2.2 虚拟鼠标实现 2.2.1 虚拟鼠标创建函数 2.2.2 鼠标移动函数 2.2.3 鼠标点击函数 2.3 mpu6050相关函数实现 2.3.1 i2c设备初始化 2.3.2 mpu6050寄存器写入 2.3.3 mpu6050寄存器读取 2.3.…...

编程日记 2025/7/5 22:05:59

Linux操作系统：信号

信号的基本介绍信号是系统响应某个条件而产生的事件，进程接收到信号会执行响应的操作； （1）信号的储存位置 vim /usr/include/x86_64-linux-gnu/bits/signum.h 旧版新版： vim /usr/include/x86_64-linux-gnu/bit…...

编程日记 2025/6/27 23:10:04

OpenCV CUDA模块特征检测与描述------用于创建一个最大值盒式滤波器（Max Box Filter）函数createBoxMaxFilter()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 createBoxMaxFilter()函数创建的是一个最大值滤波器（Maximum Filter），它对图像中每个像素邻域内的像素值取最…...

编程日记 2025/7/5 22:05:14

有没有其他影视app可以像群晖video station一样可以被Windows的本地网络驱动器找到

你是在寻找可以通过Windows本地网络（SMB共享）访问的影视媒体服务程序，就像群晖的 Video Station 一样，可以浏览、播放或挂载电影资源。以下是一些可选方案： ✅ 具备与 Synology Video Station 类似功能，并支…...

编程日记 2025/6/27 23:40:15

【神经网络与深度学习】流模型的通俗易懂的原理

流模型（Flow-based Model）简介引言流模型是一种强大的生成模型，它通过可逆变换将简单的概率分布转化为复杂的数据分布。相比于扩散模型和生成对抗网络（GAN），流模型可以精确计算数据的概率，并…...

编程日记 2025/6/27 23:14:22

OpenCV CUDA模块图像特征检测与描述------图像中快速检测特征点类cv::cuda::FastFeatureDetector

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 cv::cuda::FastFeatureDetector 是 OpenCV 的 CUDA 加速模块中的一部分，用于在图像中快速检测特征点。FAST（Features fro…...

编程日记 2025/7/5 21:44:40

分享一些多模态文档解析思路

多模态文档解析思路小记作者：Arlene 原文：https://zhuanlan.zhihu.com/p/1905635679293122466 多模态文档解析内容涉及：文本、表格和图片解析思路v1 基于mineru框架对pdf文件进行初解析其具备较完整的布局识别和内容识别，并将…...

编程日记 2025/6/27 23:32:18

【OCCT+ImGUI系列】009-Geom2d-Geom2d_AxisPlacement

一、Geom2d_AxisPlacement 简介在 OpenCASCADE 的二维几何库中，Geom2d_AxisPlacement 是一个用于定义二维坐标系的几何类，主要包含一个原点（gp_Pnt2d）和一个方向向量（gp_Dir2d）。它在构造与控制二维几何对…...

编程日记 2025/6/27 22:57:49

【深度学习:理论篇】--Pytorch之nn.Module详解

目录 1.torch.nn.Module--概述 2.torch.nn.Module--简介 3.torch.nn.Module--实现 3.1.Sequential来包装层 3.2.children和modules 1.torch.nn.Module--概述 1. PyTorch vs. Keras 的设计差异 Keras（高层框架）： 推荐通过继承 Layer 类…...

编程日记 2025/6/27 23:32:13

SQLMesh 宏操作符详解：@IF 的条件逻辑与高级应用

SQLMesh 的 IF 宏提供了一种在 SQL 查询中嵌入条件逻辑的方法，允许根据运行时条件动态调整查询结构。本文深入探讨 IF 的语法、使用场景及实际案例，帮助开发者构建更灵活、可维护的 SQL 工作流。 1. IF 宏简介 IF 是 SQLMesh 提供的条件逻辑宏&#xff…...

编程日记 2025/7/5 22:12:18

人工智能应用时代：个人成长与职业突围的底层逻辑

当人工智能从实验室走向现实场景，从概念热词变为生产力工具，一场静默却深刻的变革正在重塑人类社会的运行规则。无论是算法驱动的智能推荐、语言模型支撑的自动化创作，还是工业机器人对传统生产线的颠覆，人工智能应用已渗透至社会…...

编程日记 2025/7/5 22:05:59

STM32之串口通信蓝牙（BLE）

一、串口通信的原理与应用通信的方式处理器与外部设备之间或者处理器与处理器之间通信的方式分两种：串行通信和并行通信。串行通信传输原理：数据按位依次顺序传输（每一位占据固定的时间长度 MSB or LSB） 优点&#xff1a…...

编程日记 2025/7/5 21:59:22

【Spring Boot】配置实战指南：Properties与YML的深度对比与最佳实践

目录 1.前言 2.正文 2.1配置文件的格式 2.2properties 2.2.1基础语法 2.2.2value读取配置文件 2.2.3缺点 2.3yml 2.3.1基础语法 2.3.2配置不同数据类型 2.3.3配置读取 2.3.4配置对象和集合 2.3.5优缺点 2.4综合练习：验证码案例 2.4.1分析需求 2.4.2…...

编程日记 2025/7/5 21:58:42

数据结构篇--优先级队列排序--实验报告

实验简介框架代码实验步骤运行结果实验总结实验概述优先队列排序算法的基本思想是： 将所有待排序元素依次插入到优先队列中，然后按照从大到小的顺序，通过重复删除优先队列中的最大元素，取出所有元素，从而实现排序…...

编程日记 2025/7/5 21:48:46

【图像大模型】基于深度对抗网络的图像超分辨率重建技术ESRGAN深度解析

基于深度对抗网络的图像超分辨率重建技术ESRGAN深度解析一、技术背景与核心创新1.1 图像超分辨率技术演进1.2 核心技术创新对比二、算法原理深度解析2.1 网络架构设计2.1.1 RRDB模块结构 2.2 损失函数设计2.2.1 对抗损失（Adversarial Loss）2.2.2 感知损…...

编程日记 2025/7/5 22:00:06

Ubuntu 20.04卸载并重装 PostgreSQL

在 Ubuntu 下彻底卸载并重新安装 PostgreSQL（包括所有版本及其数据目录）的步骤下面是一个在 Ubuntu 下彻底卸载并重新安装 PostgreSQL（包括所有版本及其数据目录）的步骤。文章目录在 Ubuntu 下彻底卸载并重新安装 PostgreSQL&…...

编程日记 2025/7/5 22:04:22

1. Ruby 环境 Redis-dump 是一个 Ruby 工具，需先安装 Ruby 和 RubyGems。安装命令： sudo apt update sudo apt install ruby-full build-essential[roota29d39f5fd10:/opt/redis-dump/bin# apt install ruby-full build-essential Reading pac…...

编程日记 2025/7/5 21:53:45

AI智能分析网关V4玩手机检测算法精准管控人员手机行为，搭建智慧化安防监管体系

一、背景移动终端普及使随意用机成为常态，在生产车间、加油站、考场、手术室等场景，人员使用手机易引发生产事故、爆炸、作弊、仪器干扰等问题。传统人工巡查存在覆盖不足、响应慢、主观性强等局限，难以满足现代安全管理需求。AI智能分析…...

编程日记 2025/7/5 22:13:58

支持向量存储：PostgresSQL及pgvector扩展详细安装步骤！老工程接入RAG功能必备！

之前文章和大家分享过，将会出一篇专栏（从电脑装ubuntu系统，到安装ubuntu的常用基础软件：jdk、python、node、nginx、maven、supervisor、minio、docker、git、mysql、redis、postgresql、mq、ollama等），目前…...

编程日记 2025/7/5 21:45:39

小土堆pytorch--神经网络-非线性激活线性层及其他层介绍

1. 神经网络-非线性激活 1.1 relu与sigmoid 1.1.1 ReLU（Rectified Linear Unit，修正线性单元 ） 定义与数学表达：数学定义为 f ( x ) max ⁡ ( 0 , x ) f(x) \max(0, x) f(x)max(0,x) ，即当输入 x > 0 x > …...

编程日记 2025/7/5 22:17:52

【Vue3】数据的返回和响应式处理（ref reactive）

目录一、拉开序幕的setup 二、ref函数 2.1 访问对象的响应式处理小结：ref函数三、reactive函数 3.1 reactive同样也可以修改数组： 3.2 reactive小结： 四、Vue3中的响应式原理 4.1 vue2的响应式，对象属性的添加 4.2…...

编程日记 2025/7/5 22:02:44

【Rust智能指针】Rust智能指针原理剖析与应用指导

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，…...

编程日记 2025/7/5 21:58:42

C++ - 仿 RabbitMQ 实现消息队列（3）（详解使用muduo库）

C - 仿 RabbitMQ 实现消息队列（3）（详解使用muduo库） muduo库的基层原理核心概念总结：通俗例子：餐厅模型优势体现典型场景 muduo库中的主要类EventloopMuduo 的 EventLoop 核心解析1. 核心机制：事…...

编程日记 2025/7/5 21:45:38

Java异常处理全解析：从基础到自定义

目录 🚀前言🤔异常的定义与分类💯运行时异常💯编译时异常💯异常的基本处理 🌟异常的作用🐧自定义异常💯自定义运行时异常💯自定义编译时异常 ✍️异常的处理方案&#x1…...

编程日记 2025/7/5 22:00:06

C++初阶-vector的模拟实现2

目录 1.vector已经实现的代码总结 2.vector::resize的模拟实现 3.vector::vector(const vector& v)拷贝构造函数的模拟实现 4.vector::operator(const vector& x)的模拟实现（原始写法） 5.vector::swap的模拟实现 6.vector::operator(const …...

编程日记 2025/7/5 21:55:35

【图数据库】--Neo4j 安装

目录 1.Neo4j --概述 2.JDK安装 3.Neo4j--下载 3.1.下载资源包 3.2.创建环境变量 3.3.运行 Neo4j 是目前最流行的图形数据库(Graph Database)，它以节点(Node)、关系(Relationship)和属性(Property)的形式存储数据，专门为处理高度连接的数据而设计。…...

编程日记 2025/6/27 23:25:27

elementui初学1

当然可以！下面是从零开始创建一个最简单的 Element UI 程序的完整流程，基于 Vue 2 Element UI（如果你想用 Vue 3，请告诉我，我可以给你 Element Plus 的版本）。 ✅ 一、准备环境确保你已经安装了&#xf…...

编程日记 2025/7/5 22:22:37

lanqiaoOJ 4185：费马小定理求逆元

【题目来源】 https://www.lanqiao.cn/problems/4185/learning/ 【题目描述】给出 n，p，求。其中， 指存在某个整数 0≤a<p，使得 na mod p1，此时称 a 为 n 的逆元，即。数据保证 p 是质数且 n mod p≠0…...

编程日记 2025/6/27 23:09:23

计算机视觉与深度学习｜ Python实现CEEMDAN-ISOS-VMD-GRU-ARIMA时间序列预测（完整源码和数据)

以下是结合CEEMDAN、ISOS-VMD、GRU和ARIMA的时间序列预测的Python完整实现方案。本方案包含完整的代码、数据生成逻辑和实现细节说明。完整代码实现 import numpy as np import pandas as pd from PyEMD import CEEMDAN from vmdpy import VMD from scipy.optimize import di…...

编程日记 2025/7/3 19:51:51

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题作为前端开发者，遇到 Bug 几乎是日常。无论是样式错乱、功能异常，还是接口数据不对，Bug 总能让人头疼。但随着人工智能（AI）技术的发展&…...

编程日记 2025/7/5 14:25:11

博主总结框架

1.博主总结框架 1.1 计算机基础类（数据结构、计算机网络、操作系统等） （1）数据结构 （2）操作系统 （3）计算机网络 （4）其他物联网入门框架 1.2 计算机图形…...

编程日记 2025/7/5 22:26:52

国产化Excel处理组件Spire.XLS for .NET系列教程：通过 C# 将 TXT 文本转换为 Excel 表格

在数据处理和管理场景中，将原始文本文件（TXT）高效转换为结构化的 Excel 电子表格是一项常见要求。对于那些需要自动生成报表或者处理日志文件的开发人员而言，借助 C# 实现 TXT 到 Excel 的转换工作，可以简化数据组织和…...

编程日记 2025/7/5 21:53:02

网络安全--PHP第一天

目标熟悉信息传递架构基于phpstydy-mysql-php 前置条件需要先在数据库中创建相应的库和表名并配置表的结构该文件为数据库配置文件名字为config.php <?php $dbip localhost;//连接数据库的地址远程连接需要输入ip等 $dbuser root;//连接数据库的用户 $dbpass ro…...

编程日记 2025/6/27 23:15:05