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

5. 最长回文子串

问题

给你一个字符串 s,找到 s 中最长的 回文 子串。

示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:
输入:s = "cbbd"
输出:"bb"

分析

递推:s[i][j] = s[i-1][j-1] && s[i] == s[j],所以要枚举左边界以及右边界,从c++实现来看,枚举子串长度以及左边界,可以计算右边界,写代码比较方便。

代码

class Solution {
public:static const int N = 1e3+10;bool f[N][N]; // f[i][j]表示s[i...j]是否为回文int begin = 0, max_L = 1;int n = 0;string longestPalindrome(string s) {n = s.size();if (n < 2) {return s;}for (int i = 0; i < n; i++) {f[i][i] = true;}// 枚举子串长度for (int L = 2; L <= n; L++) {for (int i = 0; i < n; i++) { // 枚举左边界iint j = L + i - 1;if (j >= n) {break;}if (s[i] != s[j]) {f[i][j] = 0; } else {if (j - i < 3) {f[i][j] = 1; }else {f[i][j] = f[i+1][j-1]; }}if (f[i][j] && j-i+1 > max_L) {max_L = j-i+1;begin = i;}}}return s.substr(begin, max_L);}
};
http://www.hskmm.com/?act=detail&tid=22329

相关文章:

  • 基于Python+Vue开发的婚恋交友管理系统源码+运行步骤
  • 2025 年搅拌机设备厂家 TOP 企业品牌推荐排行榜,盘点磁混凝系统 / 发酵罐 / 刮泥机 / 推进式 / 脱硫侧搅拌机公司推荐!
  • 福州市 2025 国庆集训 Day1 前三题题解
  • Python常用数据类型详解:字符串、列表、字典全解析
  • 强连通,Tarjan,缩点
  • OI 笑传 #13
  • Python方案--交互式VR教育应用开发
  • 纯Qt代码实现onvif协议设备端/onvif设备模拟器/onvif虚拟监控设备/桌面转onvif
  • *补*““逆元求组合数”(费马小定理
  • C# WPF中Binding的 Source属性和ElementName属性有什么区别
  • Typora to Obsidian 迁移助手 (Typora-to-Obsidian-Migration-Helper)
  • 64. 最小路径和
  • 题解:P1020 [NOIP 1999 提高组] 导弹拦截
  • 哈希表专题
  • Meta基础设施演进与AI技术革命
  • 完整教程:Spring AI整合聊天模型DeepSeek
  • 2025 年焚烧炉厂家 TOP 企业品牌推荐排行榜!权威甄选实力与口碑俱佳的江苏焚烧炉 / 无锡焚烧炉推荐这十家公司!
  • 2025 年防腐涂料厂家 TOP 企业品牌推荐排行榜,乙烯基、环氧煤沥青、环氧防腐涂料、防腐涂料地坪 、防腐涂料水池推荐这十家公司!
  • 2025双氧水厂家权威推荐榜:优质供应与专业定制实力之选
  • Win环境下包管理工具
  • MX Round 11 解题报告
  • 用 C# 打造企业资产管理系统雏形——从控制台到完整模块设计 - 详解
  • java开发之微信机器人的二次开发
  • 10.1刷题计划一
  • 笔记本电脑重装系统后找不到5G WIFI无线网或蓝牙模块消失的解决方案
  • 菜鸟坚持记录-开头篇
  • AI+传统工作流:Photoshop/Excel的智能插件开发指南 - 实践
  • Typora 笔记迁移 Obsidian 图片附件库批量移动方法,适用于笔记整理。
  • 2025年确有专长培训权威推荐榜:专业资质与特色诊疗口碑之选
  • 开源 C# 快速构建(五)自定义控件--仪表盘