关于最长回文串的问题
2021/8/20 23:10:07
本文主要是介绍关于最长回文串的问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 这两题都属于区间dp问题
- 他不和最长公共子序列一样,回文串需要对比区间内首位字符,所以就决定了他只能从中间向两边扩散
- 最后的代码会发现:只是状态转移的时候赋值问题,子序列不必连续,所以需要去找最大的,而子串连续,只要不相同,这个区间就不是回文串.
516. 最长回文子序列
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
解析:两个字符比较的时候我们需要分别记录每一个字符串的位置,然后去维护dp数组,直到两个串遍历完,
这一题是求一个串的最大回文序列,可以不连续,结果是这个串有,我们化解成子问题就是从最开始的子串长度为一开始,一步一步增加,属于区间dp,搞清楚转移方程和初始化后,看一看原始数组,然后在决定怎么遍历.
class Solution { public: //区间dp int longestPalindromeSubseq(string s) { int len = s.size(); vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0)); for(int i = 0; i < len; i++) { dp[i][i] = 1; } for(int i = 1; i < len; i++) { for(int j = i - 1; j >= 0; j--) { if(s[i] == s[j]) { dp[i][j] = dp[i - 1][j + 1] + 2; }else { dp[i][j] = max(dp[i][j + 1], dp[i - 1][j]); } } } return dp[len - 1][0]; } };
5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
class Solution { public: string longestPalindrome(string s) { int len = s.size(); vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0)); for(int i = 0; i < len; i++) { dp[i][i] = 1; } int ans = 0; int start = 0,end = 0; for(int i = 1; i < len; i++) { for(int j = i - 1; j >= 0; j--) { if(s[i] == s[j]) { if(i - j == 1) dp[i][j] = 1; else dp[i][j] = dp[i - 1][j + 1]; } if (dp[i][j] && ans < (i - j + 1)) { ans = (i - j + 1); start = j,end = i; } } } return s.substr(start, end - start + 1); } };
这篇关于关于最长回文串的问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)