给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd"
输出: "bb"来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
方法1：动态规划
最优子结构：当一个串是一个回文串的时候，在其头尾各加一个相同的字符组成的新字符串依旧是一个回文串
dp[i][j]=1，代表从下标i到下标j组成的字符串是一个回文串
如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1
初始化：
1.对于一个字符的回文串：dp[i][i]=1
2.对于两个字符的回文串：如果s[i]==s[i+1]，那么dp[i][i+1]=1
对于三个字符的回文串：如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1
时间复杂度：O(N^2)
空间复杂度：O(N^2)
class Solution { public: string longestPalindrome(string s) { if(s.size()==0) return ""; if(s.size()==1) return s; if(s.size()==2&&s[0]==s[1]) return s; int n=s.length(); int dp[n+1][n+1]; memset(dp,0,sizeof(dp)); int ans=1; int start=0; for(int i=0;i<n;i++) { dp[i][i]=1; } for(int i=0;i<n-1;i++) { if(s[i]==s[i+1]) { dp[i][i+1]=1; ans=2; start=i; } } int l=3; while(l<=n) { for(int i=0;i<n-l+1;i++) { int j=i+l-1; if(dp[i+1][j-1]==1&&s[i]==s[j]) { dp[i][j]=1; start=i; ans=l; } } l++; } return s.substr(start,ans); } };
方法2：中心扩展法
将每个字符当作回文串的中心，然后往两边扩展，取扩展得到的回文串的最大值就是最长回文子串
考虑到回文串的奇偶情况，我们可以算两种情况：以一个字符为回文串的中心，以两个字符为回文串的中心，然后去二者最大值就可以
时间复杂度：O(N^2),以每个字符为中心需要遍历一次，然后每次都需要往两边扩展
空间复杂度：O(1),只需要用到一些常量
class Solution { public: int f1(string str,int left,int right,int n) { int c=1; //cout<<"left="<<left<<" right="<<right<<" n="<<n<<endl; left--; right++; while(left>=0&&right<n&&str[left]==str[right]) { left--; right++; c+=2; } return c; } int f2(string str,int left,int right,int n) { int c=0; if(str[left]==str[right]) c=2; else { c=1; return c; } left--; right++; while(left>=0&&right<n&&str[left]==str[right]) { left--; right++; c+=2; } return c; } string longestPalindrome(string s) { int n=s.size(); if(n==0) return ""; if(n==1) return s; if(n==2&&s[0]==s[1]) return s; int ans=1; int start=0; for(int i=0;i<n-1;i++) { int x1=f1(s,i,i,n); int x2=f2(s,i,i+1,n); //cout<<"i="<<i<<" x1="<< x1<<" x2="<<x2<<endl; if(max(x1,x2)>ans) { ans=max(x1,x2); //cout<<"ans="<<ans<<endl; if(ans%2==1) start=i-ans/2; else start=i-(ans-2)/2; //cout<<"start="<<start<<endl; } } return s.substr(start,ans); } };
还有一个解决方案是马拉车算法
时间复杂度为O(N)!!!
但是我目前也没有掌握，就没有贴出来，怕误导别人