|
5. 最长回文子串
给你一个字符串?s，找到?s?中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
自己之所以想把这道题给记录下来是因为写这道题的时候，自己卡了很久。
解法一：暴力解法
取出每一个字串，然后判断子串是否是回文数。
int IsPalidrome(char *s, int num)//判断传进来得字符串是不是回文数
{
int left = 0, right = num-1;
while (left<right) {
if (s[left] != s[right]) {
return -1;
}
left++;
right--;
}
return num;
}
char * longestPalindrome(char * s)
{
int numSize = strlen(s);
if (numSize<2) {
return s;
}
char out[1000] = {0};
int i = 0, j = 0;
int k = 0;
int maxlen = 1;
int startIndex = 1;
for ( i = 0; i < numSize; i++) {
for ( j = i; j <numSize; j++) {
/*strncpy(out, s + i, j - i+1);
out[j - i + 1] = 0;*/
substr(out, s, i, j - i + 1);
printf("%s\n", out);
if (j-i+1>maxlen&&(IsPalidrome(out,j-i+1)!=-1)) {
maxlen = j - i + 1;
startIndex = i;
}
}
printf("\n");
}
char *p = (char*)malloc(sizeof(char)*(maxlen + 1));
substr(p, s, startIndex, maxlen);
return p;
}
int main(void)
{
char str[1000] = "ac";
char *ret=NULL;
ret = longestPalindrome(str);
printf("最长的回文串：%s", ret);
return 0;
}
int substr(char *dst, char *src, int start, int len)//取字符串中得字串，具体见上一条博客
{
int i = 0;
if (dst==NULL) {
return -1;
}
for ( i = 0; i < len; i++) {
dst[i] = src[i + start];
}
dst[len] = '\0';
return 0;
}
这也是一开始想到的最麻烦的，也是最暴力的解法，但是不用测试，肯定是时间不通过，而且令我不解的是，为什么题目举得例子，babab，bab就算，babab不算，难道是因为不能称得上子串？
不管了，暴力解法就当练习取字符串了。
第二种解法：中心扩散法：
具体思想就是：遍历每一个单个字符，然后往字符的两边扩散，扩散应该分奇偶，也就是分别对应zbbz，或者aba这样的字符。
int expandCenter(char *str, int left, int right, int len)
{
/*回文字串分为两种abba和aba类型。即考虑奇偶*/
/*当是偶数时，中间的两个相同*/
while (left>=0&&right<len) {
if (str[left] == str[right]) {
left--;
right++;
}
else {
break;
}
}
return right - left -1;
}
char * longestPalindrome(char * s)
{
int length = strlen(s);
if (length<2) {
return s;
}
int maxlen = 1;
int startIndex = 0;
for (int i = 0; i < length; i++) {
int odd = expandCenter(s, i, i, length);
int even = expandCenter(s, i, i + 1, length);
int newMaxlen = odd > even ? odd : even;
if (newMaxlen>maxlen) {
maxlen = newMaxlen;
startIndex = i-(maxlen-1)/2;
}
}
s[startIndex + maxlen] = 0;
return s + startIndex;
}
int main(void)
{
char str[1000] = "bb";
char *ret=NULL;
ret = longestPalindrome(str);
printf("最长的回文串：%s", ret);
return 0;
}
|