leetcode day4 409+5

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;
}