LeetCode -Java 516. 最长回文子序列
发布日期:2021-06-20 05:37:12
浏览次数:11
分类:技术文章
本文共 823 字,大约阅读时间需要 2 分钟。
给定一个字符串s
,找到其中最长的回文子序列。可以假设s
的最大长度为1000
。
示例 1:
输入:"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
分析:
最小回文子串:子串是连续的。最小回文子序列:可以去掉几个字符。本题类似最小回文子串,采用动态规划,我们假设dp[ i ] [ j ]表示从S字符串中第i到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; --S[i] ==S[j] 字符相等,长度为内侧子串长度+2
代码:
import java.util.*;/** * @author: Mr.Hu */public class Main{ public static void main(String[] args) { Scanner sc =new Scanner(System.in); System.out.println(longestPalindrome(sc.next())); } public static int longestPalindrome(String s) { if (s.length()==0) return 0; int dp[][]=new int[s.length()][s.length()]; //记录回文子序列长度 for (int i = 0; i < s.length(); i++) { //初始化长度为1和2的dp dp[i][i]=1; if (i
转载地址:https://blog.csdn.net/h2453532874/article/details/88647669 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月19日 13时32分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3
2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法
2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳
2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法
2019-04-21
java bss_[转] .bss段和.data段的区别
2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏
2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识
2019-04-21
java给xyz大小排序_java递归实现string xyz排序
2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答
2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题
2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置
2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用
2019-04-21
java实验一目的_Java实验报告(实验一)
2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽
2019-04-21
Java 去除空格获取文件路径
2019-04-21
python 批量修改文件名称去除文件名中空格
2019-04-21
python 将文件名写入 txt文件
2019-04-21