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

【动态规划刷题 17】回文子串 最长回文子串

647. 回文子串

链接: 647. 回文子串
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:

输入:s = “aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

解法(动态规划):
算法思路:
我们可以先「预处理」⼀下,将所有⼦串「是否回⽂」的信息统计在 dp 表⾥⾯,然后直接在表⾥⾯统计 true 的个数即可。

1.状态表示*
为了能表⽰出来所有的⼦串,我们可以创建⼀个 n * n 的⼆维 dp 表,只⽤到「上三⻆部分」
即可。
其中, dp[i][j] 表⽰: s 字符串 [i, j] 的⼦串,是否是回⽂串。

2.状态转移方程
对于回⽂串,我们⼀般分析⼀个「区间两头」的元素:

  1. 当 s[i] != s[j] 的时候:不可能是回⽂串, dp[i][j] = 0 ;
  2. 当 s[i] == s[j] 的时候:根据⻓度分三种情况讨论:
    • ⻓度为 1 ,也就是 i == j :此时⼀定是回⽂串,dp[i][j] = true ;
    • ⻓度为 2 ,也就是 i + 1 == j :此时也⼀定是回⽂串, dp[i][j] =true ;
    • ⻓度⼤于 2 ,此时要去看看 [i + 1, j - 1] 区间的⼦串是否回⽂: dp[i][j]= dp[i + 1][j - 1] 。

综上,状态转移⽅程分情况谈论即可。

3. 初始化
因为我们的状态转移⽅程分析的很细致,因此⽆需初始化。

4. 填表顺序
根据「状态转移⽅程」,我们需要「从下往上」填写每⼀⾏,每⼀⾏的顺序⽆所谓

5. 返回值
根据「状态表⽰和题⽬要求」,我们需要返回 dp 表中 true 的个数

代码:

 int countSubstrings(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));dp[0][0]=1;int sum=1;for(int j=1;j<n;j++){for(int i=0;i<=j;i++){if(s[j]==s[i]){if(j==i||j==i+1) dp[i][j]=1;if(j-i>1){dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]) sum++;}}return sum;}

在这里插入图片描述

5. 最长回文子串

链接: 5. 最长回文子串

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

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

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

输入:s = “cbbd”
输出:“bb”

解法思路:

  • a. 我们可以先⽤ dp 表统计出「所有⼦串是否回⽂」的信息
  • b. 然后根据 dp 表⽰ true 的位置,得到回⽂串的「起始位置」和「⻓度」。 那么我们就可以在表中找出最⻓回⽂串。

关于「预处理所有⼦串是否回⽂」,已经在上⼀道题⽬⾥已经讲解过了。

代码:

  string longestPalindrome(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));dp[0][0]=1;int sum=1;string ret(1,s[0]);for(int j=1;j<n;j++){for(int i=0;i<=j;i++){if(s[j]==s[i]){if(j==i||j==i+1) dp[i][j]=1;if(j-i>1){dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]){if(j-i+1>sum){sum=j-i+1;string tmp(s.begin()+i,s.begin()+j+1);ret=tmp;}}}}return ret;}

在这里插入图片描述

相关文章:

【动态规划刷题 17】回文子串 最长回文子串

647. 回文子串 链接: 647. 回文子串 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&#xff0c;即使是由…...

mysql 每日自动备份数据库

在 MySQL 中&#xff0c;你可以使用定时任务来每日自动备份数据库。通常&#xff0c;最常用的方法是使用操作系统的定时任务工具&#xff08;如cron&#xff09;来调度备份操作。以下是一些步骤来设置每日定时备份MySQL数据库&#xff1a; 创建备份脚本&#xff1a;首先&#x…...

【计算机网络】图解路由器(二)

本系列包含&#xff1a; 图解路由器&#xff08;一&#xff09;图解路由器&#xff08;二&#xff09; 图解路由器&#xff08;二&#xff09; 21、什么是静态路由&#xff1f;22、什么是动态路由&#xff1f;23、动态路由有哪些类型&#xff1f;24、什么是 RIP &#xff1f;2…...

流媒体及直播相关知识

文章目录 前言一、流媒体1、基本概念2、流式传输3、流媒体技术原理4、流媒体传输模式5、H.264 流媒体传输系统框架 二、直播1、直播中使用的流媒体协议2、直播的模块划分3、视频直播流程①、推流到服务器②、服务器流分发 前言 本文主要讲解流媒体及其直播相关知识&#xff0c…...

数据治理-数据资产估值

数据生命周期大多数阶段涉及成本。数据只有使用时才有价值&#xff0c;使用时数据还产生与风险相关的成本。因此&#xff0c;当使用数据的经济效益超过了上述成本时&#xff0c;就会显现其价值。 其他的度量价值的方式包括&#xff1a; 替换成本。数据替换或恢复的成本。包括组…...

点云从入门到精通技术详解100篇-机载 LiDAR 点云滤波及分类

目录 前言 国内外研究现状 点云滤波研究现状 点云分类研究现状...

【SLAM】 前端-视觉里程计之相对位姿估计

【SLAM】 前端-视觉里程计之相对位姿估计 1.相对位姿估计 在前端视觉里程计中&#xff0c;相对位姿估计是指通过视觉传感器&#xff08;例如相机&#xff09;捕捉的图像信息&#xff0c;来估计相机相对于先前位置的位姿&#xff08;位置和姿态&#xff09;变化。这种估计通常…...

git format-patch打补丁

git format-patch HEAD^ 这个命令会产生从倒数第二个提交 HEAD^ 到最后提交 HEAD 之间所有提交的差异&#xff0c;并生成一个包含这些差异的补丁文件。这是一个包含详细步骤的例子&#xff1a; 第一步&#xff0c;创建一个新的 git 仓库并进行一些提交。这些提交是我们稍后会生…...

大数据Flink(八十三):SQL语法的DML:With、SELECT WHERE、SELECT DISTINCT 子句

文章目录 SQL语法的DML:With、SELECT & WHERE、SELECT DISTINCT 子句 一、DML:With 子句...

C++:list

目录 List的模拟实现 List节点类 List链表结构 List迭代器类 结构 T& operator*(); T& operator->(); Self& operator(); Self operator(int); Self& operator--(); Self& operator--(int); bool operator!(const Self& l); bool oper…...

【C++】搜索二叉树底层实现

目录 一&#xff0c;概念 二&#xff0c;实现分析 1. 插入 &#xff08;1.&#xff09;非递归版本 &#xff08;2.&#xff09;递归版本 2. 打印搜索二叉树 3.查找函数 &#xff08;1.&#xff09;非递归版本 &#xff08;2.&#xff09;递归版本 4. 删除函数&#x…...

C8051F020 SMBus一直处于busy状态解决办法

当SMBus总线处于busy状态切且无法自动释放时&#xff0c;SMB0CN寄存器的第7位一直为 1&#xff0c;总线没有释放。 SMBus总线释放超时的一个纠错机制&#xff0c;它允许SMBus状态机在 SDA 和 SCL 信号线同为高电平超过 10个SMBus时钟源周期后判断总线为释放状态。 如果总线释放…...

Activiz 9.2 for Linux Crack

Activiz 9.2 在 C#、.Net 和 Unity 软件中为您的 3D 内容释放可视化工具包的强大功能。 ActiViz 允许您轻松地将 3D 可视化集成到您的应用程序中。 ActiViz 功能 用 C# 封装的 3D 可视化软件系统 允许在 .NET 环境中快速开发可投入生产的交互式3D 应用程序 支持窗口演示基础 (…...

数据结构 - 链表

线性表的链式存储结构 概念 将线性表 L (a0, a1, … , an-1)中各元素分布在存储器的不同存储块&#xff0c;成为结点&#xff0c;通过地址或指针建立元素之间的联系。 结点的 data 域存放数据元素 ai &#xff0c;而 next 域是一个指针&#xff0c;指向 ai 的直接后继 ai1 …...

Android 12 Bluetooth源码分析蓝牙配对

本文主要是列出一些蓝牙配对重要的类和方法/函数&#xff0c;遇到相关问题时方便查找添加log排查。 蓝牙扫描列表页面&#xff1a;packages/apps/Settings/src/com/android/settings/bluetooth/DeviceListPreferenceFragment.java点击其中一个设备会调用&#xff1a;onPrefere…...

Python异步编程并发执行爬虫任务,用回调函数解析响应

一、问题&#xff1a;当发送API请求&#xff0c;读写数据库任务较重时&#xff0c;程序运行效率急剧下降。 异步技术是Python编程中对提升性能非常重要的一项技术。在实际应用&#xff0c;经常面临对外发送网络请求&#xff0c;调用外部接口&#xff0c;或者不断更新数据库或文…...

React组件化开发

1.组件的定义方式 函数组件Functional Component类组件Class Component 2.类组件 export class Profile extends Component {render() {console.log(this.context);return (<div>Profile</div>)} } 组件的名称是大写字符开头&#xff08;无论类组件还是函数组件…...

LuatOS-SOC接口文档(air780E)--crypto - 加解密和hash函数

crypto.md5(str) 计算md5值 参数 传入值类型 解释 string 需要计算的字符串 返回值 返回值类型 解释 string 计算得出的md5值的hex字符串 例子 -- 计算字符串"abc"的md5 log.info("md5", crypto.md5("abc"))crypto.hmac_md5(str, k…...

自动化测试的定位及一些思考

大家对自动化的理解&#xff0c;首先是想到Web UI自动化&#xff0c;这就为什么我一说自动化&#xff0c;公司一般就会有很多人反对&#xff0c;因为自动化的成本实在太高了&#xff0c;其实自动化是分为三个层面的&#xff08;UI层自动化、接口自动化、单元测试&#xff09;&a…...

展会动态 | 迪捷软件邀您参加2023世界智能网联汽车大会

*9月18日之前注册的观众免收门票费* 由北京市人民政府、工业和信息化部、公安部、交通运输部和中国科学技术协会联合主办的2023世界智能网联汽车大会将于9月21日-24日在北京中国国际展览中心&#xff08;顺义馆&#xff09;举行。 论坛背景 本届展会以“聚智成势 协同向新——…...

导师推荐!盘点2026年当红之选的AI论文平台

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文平台&#xff0c;覆盖选题构思、文献综述、数据整理、降重润色、格式排版等全流程&#xff0c;高效搞定论文&#xff0c;让你轻松应对学术挑战。 一、全流程王者&#xff1a;一站式搞定论文全链…...

xLearn性能优化秘籍:SSE指令加速与内存管理技巧

xLearn性能优化秘籍&#xff1a;SSE指令加速与内存管理技巧 【免费下载链接】xlearn High performance, easy-to-use, and scalable machine learning (ML) package, including linear model (LR), factorization machines (FM), and field-aware factorization machines (FFM)…...

SEO网站推广的发展历程是怎样的

<h2>SEO网站推广的发展历程&#xff1a;从初始阶段到现代优化</h2> <p>随着互联网的迅速发展&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;作为网站推广的重要手段&#xff0c;经历了漫长而复杂的发展历程。SEO的进化不仅改变了网站如何被搜索引擎索…...

单片机入门到实践:51系列开发全攻略

单片机从零入门到项目实践的技术路径1. 单片机学习基础准备1.1 必备知识体系学习单片机开发需要构建以下基础知识框架&#xff1a;电路基础&#xff1a;包括欧姆定律、基尔霍夫定律等基本电路理论数字电路&#xff1a;逻辑门电路、时序电路、组合逻辑电路等模拟电路&#xff1a…...

源码编译实战:定制rpath与interpreter实现高版本glibc程序向下兼容部署

1. 为什么需要高版本glibc程序向下兼容 最近在给客户部署AI推理服务时遇到一个典型问题&#xff1a;开发环境用的是Ubuntu 20.04&#xff08;glibc 2.31&#xff09;&#xff0c;而生产环境是CentOS 7&#xff08;glibc 2.17&#xff09;。直接拷贝编译好的程序运行时&#xff…...

InnoDB 事务 undo log 与 MVCC 可视化讲解(画流程图+伪代码)

InnoDB 事务 undo log 与 MVCC 可视化讲解(画流程图+伪代码) 前言 在MySQL的InnoDB存储引擎中,事务的四大特性(ACID)是其核心能力之一。其中,隔离性(Isolation)和一致性(Consistency)的实现离不开undo log与MVCC(多版本并发控制)的精妙设计。 本文将从底层原理出…...

Zap vs Go:终极后端性能对比测试与实战分析

Zap vs Go&#xff1a;终极后端性能对比测试与实战分析 【免费下载链接】zap blazingly fast backends in zig 项目地址: https://gitcode.com/gh_mirrors/zap/zap Zap 作为一款基于 Zig 语言开发的后端框架&#xff0c;以其 "blazingly fast backends" 为核心…...

Notepad2终极指南:轻量级文本编辑器的完整使用教程

Notepad2终极指南&#xff1a;轻量级文本编辑器的完整使用教程 【免费下载链接】notepad2 Notepad2-zufuliu is a light-weight Scintilla based text editor for Windows with syntax highlighting, code folding, auto-completion and API list for many programming languag…...

OpenWrt固件下载与配置教程:R5S设备从入门到精通

OpenWrt固件下载与配置教程&#xff1a;R5S设备从入门到精通 【免费下载链接】openwrt openwrt编译更新库X86-R2C-R2S-R4S-R5S-N1-小米MI系列等多机型全部适配OTA自动升级 项目地址: https://gitcode.com/GitHub_Trending/openwrt5/openwrt GitHub_Trending/openwrt5/op…...

WSL2下git clone失败:防火墙与代理配置全解析

1. WSL2下git clone失败的常见现象 最近在WSL2环境下工作时&#xff0c;突然发现git clone命令无法正常拉取远程仓库代码。这个问题困扰了我好几天&#xff0c;经过反复排查才发现是Windows防火墙设置和代理配置的问题。相信很多使用WSL2开发的同行都遇到过类似情况&#xff1…...