【Leetcode刷题Python】516. 最长回文子序列
1 题目
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = “bbbab”
输出:4
解释:一个可能的最长回文子序列为 “bbbb” 。
示例 2:
输入:s = “cbbd”
输出:2
解释:一个可能的最长回文子序列为 “bb” 。
2 解析
和leetcoe 1143题思路一样的,区别在于,只需要将字符串逆转,求最长公共子序列即可。
求最长公共子序列的思路如下
思路:如果
t
e
x
t
1
[
i
]
=
=
t
e
x
t
2
[
j
]
text1[i]==text2[j]
text1[i]==text2[j],则在矩阵中是从左上角往右下角沿着对角线移动,如果不等于,即i+1或者j+1的情况时,在矩阵中是右移和下移。所以状态转移是,两种情况,第一种,相等,则dp+1,向右下角移动,不相等,取前上面和左边的dp中最大值。
状态: dp[i][j]表示i行j列的矩阵中,最长的公共子数组
状态转移:
dp
[
i
]
[
j
]
=
{
dp
[
i
−
1
]
[
j
−
1
]
+
1
,
text
1
[
i
−
1
]
=
text
2
[
j
−
1
]
max
(
dp
[
i
−
1
]
[
j
]
,
dp
[
i
]
[
j
−
1
]
)
,
text
1
[
i
−
1
]
≠
text
2
[
j
−
1
]
\textit{dp}[i][j] = \begin{cases} \textit{dp}[i-1][j-1]+1, & \textit{text}_1[i-1]=\textit{text}_2[j-1] \\ \max(\textit{dp}[i-1][j],\textit{dp}[i][j-1]), & \textit{text}_1[i-1] \ne \textit{text}_2[j-1] \end{cases}
dp[i][j]={dp[i−1][j−1]+1,max(dp[i−1][j],dp[i][j−1]),text1[i−1]=text2[j−1]text1[i−1]=text2[j−1]
最终计算得到dp[m][n] 即为text1和text2的最长公共子序列的长度。
3 python实现
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
s2 = s[::-1]
n = len(s)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if s[i-1]==s2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[n][n]
相关文章
- 如何为pycharm配置Python解释器_pycharm选择python解释器
- Python学生信息管理系统(界面版)
- python十进制转换_Python 进制转换
- python人工智能学习笔记_[Python] 人工智能与自然语言处理学习笔记(1)[通俗易懂]
- Python入门系列(五)一篇搞懂python语句
- python socket recvfrom_Python:socket.recvfrom()不返回任何地址
- python chr()和ord()_Python函数ord
- Python 技巧篇-pip卸载python库实例演示,查看pip命令大全方法[通俗易懂]
- python 截取图片的某个区域_python读取文件夹下所有文件
- python抛出异常写法_零基础学 Python(32):如何抛出和捕获异常?「建议收藏」
- python中if判断语句的用法_Python if判断语句的用法详细介绍[通俗易懂]
- 【测试开发】python系列教程:Python 运算符
- 纯 Python 实现的图片压缩工具
- 新手学Python可行吗?需要什么基础?(新手学python可行吗?需要什么基础)
- python-Python与PostgreSQL数据库-使用Python执行PostgreSQL查询(二)
- Python setattr()、getattr()、hasattr()函数用法详解
- python播放wav音频文件代码详解编程语言
- Python输出函数print()总结(python print())详解编程语言
- 无敌了,不需要操作系统就能运行 Python 了!
- 添加声音到你的 Python 游戏
- PyTorch 1.8发布,支持 AMD GPU 和 Python
- python求素数示例分享
- Python实现的几个常用排序算法实例