409 最长回文串
给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的
回文串
的长度。
在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例 1:
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = "a"
输出:1
解释:可以构造的最长回文串是"a",它的长度是 1。
提示:
1 <= s.length <= 2000
s 只由小写 和/或 大写英文字母组成
解题思路:注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
把所有偶数的加起来,奇数的加上它-1的偶数,如果最后长度小于字符串长度,说明还可以加一个数。
int longestPalindrome(char* s) {int sz=strlen(s);int a[26]={};int b[26]={};for(int i=0;i<sz;i++){if(a[i]>='A'&&a[i]<='Z')a[s[i]-'A']++;else b[s[i]-'a']++;}int sum=0;for(int i=0;i<26;i++){if(a[i]%2==0)sum+=a[i];else sum=sum+a[i]-1;if(b[i]%2==0)sum+=b[i];else sum=sum+b[i]-1;}if(sum!=sz)sum++;return sum;
}
———————题目分割线——————
5 最长回文子串
给你一个字符串 s,找到 s 中最长的 回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
方法一:暴力求解
start:子串起始位置,求出最长回文子串后,s[start+len]='\0',原地修改返回
最后返回s+start
分回文子串是奇数和偶数讨论,注意考虑越界情况
(1)奇数 left=i-1,right=i+1
向两侧扩散 a[left]=a[right],left--,right++
len=right-left-1与len比大小,大于则更新len和start的值
(2)偶数,left=i.right=i+1
与奇数同理
char* longestPalindrome(char* s) {int sz=strlen(s),start=0,len=0;for(int i=0;i<sz;i++){int left=i-1,right=i+1;while(left>=0&&right<sz&&s[left]==s[right] ){left--;right++;}if(right-left-1>len){len=right-left-1;start=left+1;}}for(int i=0;i<sz;i++){int left=i,right=i+1;while(left>=0&&right<sz&&s[left]==s[right]){left--;right++;}if(right-left-1>len){len=right-left-1;start=left+1;}}s[start+len]='\0';return s+start;
}
方法二:动态规划
dp[i][j]=1表示从i到j是回文串
1、初始化,dp[i][i]=1
2、依此检测长度为2,3...s.length的字符串是否是回文串
首尾相等的两种情况
(1)字符长度为2,3,就一定是回文串
(2)字符长度>3,dp[i][j]=dp[i+1][j-1]
char* longestPalindrome(char* s) {int sz=strlen(s),start=0,maxl=1;int dp[sz][sz]={};for(int i=0;i<sz;i++){dp[i][i]=1;}for(int len=2;len<=sz;len++){for(int i=0;i<sz;i++){int j=i+len-1;if(j>=sz)break;//注意越界情况if(s[i]==s[j]){if(len<=2)dp[i][j]=1;else dp[i][j]=dp[i+1][j-1];}if(dp[i][j]==1&&len>maxl){maxl=len;start=i;}}}s[start+maxl]='\0';return s+start;
}