#leetcode刷题之路5-最长回文子串
2019-02-27 11:51:16来源:博客园 阅读 ()
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
思路一:暴力法,不说了
思路二:动态规划
参考官方给的思路:
How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
#include <iostream> #include <vector> using namespace std; string longestPalindrome(string s) { int len=s.length(); //std::cout << "len="<<len<< std::endl; int num=1;//记录长度 int flag=0;//记录起始位置 if(len==0) return ""; if(len==1) return s; //字符串只有一个的话返回那一个字符 vector< vector<int> > palindrome(len,vector<int>(len));//用于存储回文信息,全部初始为0 //int *palindrome=new int[len][len]; //首先这里考虑如果整个字符串都没有回文序列,那么就返回任意一个符号,如果有两个挨着的字符相同,那么就返回其中一组 for(int i=0;i<len;i++) { palindrome[i][i]=1; if((i<len-1)&&s[i]==s[i+1]) { palindrome[i][i+1]=1; num=2; flag=i; } } for (int new_num = 3; new_num <= len; new_num++)//接着从3开始设置子串的长度 { for (int j = 0; j+new_num-1 < len; j++)//枚举子串的起始点 { if (s[j] == s[j+new_num-1] && palindrome[j+1][j+new_num-1-1]==1)//有点递归的感觉 { palindrome[j][j+new_num-1] = 1; flag=j; num = new_num; } } } return s.substr(flag,num); } int main() { std::string s="ac"; string ss=longestPalindrome(s); std::cout << ss << std::endl; return 0; }
C++二维数组动态申请内存
原文链接:https://www.cnblogs.com/biat/p/10440644.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- OI之路 2019-10-25
- 小白的C++之路——求质数 2019-10-25
- #leetcode刷题之路19-删除链表的倒数第N个节点 2019-03-13
- #leetcode刷题之路17-电话号码的字母组合 2019-03-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash