代码随想录 Day - 59|#647 回文字串|#516 最长回文子序列

news/2025/2/15 21:56:47/

清单

● 647. 回文字串
● 516. 最长回文子序列

LeetCode #647 回文字串

1. 题目

给你一个字符串 s ,请你统计并返回这个字符串中回文子串的数目。
回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串

2. 思路

需要判断回文字符串(正着读和倒过来读)采用二维数组
增加一个result 参数用于记录True个数 最后return result 即为答案

  1. dp含义: s[i] (正着读) 和 s[j] (倒着读) 能否形成回文字符串
  2. 递推公式 :
    • s[i] != s[j] —> dp[i][j] = False
    • s[i] == s[j]:
      1. j - i <=1 ----> dp[i][j] = True
      1. j - i > 1 -----> dp[i][j] = dp[ i+1 ][ j-1 ]
  3. 初始化: dp[0][0] = False
  4. 遍历顺序: 因为j为倒着读 因此遍历顺序为从下至上 从左往右(类比双指针)

3. 代码实现

class Solution:def countSubstrings(self, s: str) -> int:#Initial dpdp = [[False] * len(s) for _ in range(len(s))]result = 0for i in range(len(s)-1, -1, -1):for j in range(i, len(s)):if s[i] == s[j]:if j - i <= 1:dp[i][j] = Trueresult += 1elif dp[i+1][j-1]:dp[i][j] = Trueresult += 1return result

LeetCode #516 最长回文子序列

1. 题目

给你一个字符串 s,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

2. 思路

需要统计回文字符串长度(正着读和倒过来读)采用二维数组

  1. dp含义: s[i] (正着读) 和 s[j] (倒着读) 形成的回文字符串长度为dp[i][j]
  2. 递推公式 :
    • s[i] != s[j] —> dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    • s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  3. 初始化: dp[0][0] = 0, dp[i][i] = 1
  4. 遍历顺序: 因为j为倒着读 因此遍历顺序为从下至上 从左往右(类比双指针)

3. 代码实现

class Solution:def longestPalindromeSubseq(self, s: str) -> int:#Initial dpdp = [[0] * len(s) for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1, -1, -1):for j in range(i + 1, len(s)):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1] + 2 else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][-1]

http://www.ppmy.cn/news/1137888.html

相关文章

typora + picgo + 对象存储 OSS

文章目录 一、安装软件二、使用阿里云 oss 存储图片三、picgo 设置四、typora 设置自动上传 一、安装软件 Typora1.3.8 &#xff08;安装即破解&#xff09; picgo 2.3.0 安装 阿里云盘&#xff08;软件安装包&#xff09;&#xff1a; https://www.aliyundrive.com/s/saQoS…

Python与正则表达式

我们在做机器学习项目的时候&#xff0c;很大部分的精力都在做数据的整理&#xff0c;不管是用爬虫在网上爬取数据还是对已有的数据进行整理&#xff0c;往往需要对一些特定的字符串进行处理&#xff0c;正则表达式则是进行数据处理的利器。 一、什么是正则表达式 正则表达式…

GPT系列论文解读:GPT-2

GPT系列 GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一系列基于Transformer架构的预训练语言模型&#xff0c;由OpenAI开发。以下是GPT系列的主要模型&#xff1a; GPT&#xff1a;GPT-1是于2018年发布的第一个版本&#xff0c;它使用了12个Transformer…

Java常见API---split()

package daysreplace;public class SplitTest {public static void main(String[] args) {String str"武汉市|孝感市|长沙市|北京市|上海市";String[] array str.split("\\|");System.out.println(array[0]);System.out.println(array[1]);System.out.pri…

【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

&#x1f440;樊梓慕&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 &#x1f31d;每一个不曾起舞的日子&#xff0c;都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占…

C++笔记之信号量、互斥量与PV操作

C笔记之信号量、互斥量与PV操作 文章目录 C笔记之信号量、互斥量与PV操作1.信号量概念2.信号量例程一3.信号量例程二4.信号量例程三5.互斥量6.PV操作概念7.PV操作详解——抄自&#xff1a;https://mp.weixin.qq.com/s/vvjhbzsWQNRkU7-b_dURlQ8.PV操作的英文全称 1.信号量概念 …

python 打包可执行文件-pyinstaller详解

python 打包可执行文件-pyinstaller详解 引言一、参数详解二、优化代码三、体积压缩 引言 pyinstaller是一个将python程序打包成独立可执行文件&#xff08;exe&#xff0c;app等&#xff09;的工具&#xff0c;它具有跨平台兼容性&#xff0c;可以在windows&#xff0c;mac和…

C++11各种锁的具体使用

1.什么是互斥量&#xff08;锁&#xff09;&#xff1f; 互斥量在实际开发中很常用&#xff0c;需要学习了解&#xff01; 这样比喻&#xff1a;单位上有一台打印机&#xff08;共享数据a&#xff09;&#xff0c;你要用打印机&#xff08;线程1要操作数据a&#xff09;&#…