Leetcode 5 -- Longest Palindromic Substring

题目

Given a string S, find the longest palindromic substring in S. You may
assume that the maximum length of S is 1000, and there exists one unique
longest palindromic substring.

题意

从字符串中找出最长回文子串,将其另存新串,返回指针

思路

回文串只有两种类型,长度为偶数和长度为奇数型
遍历字符串s:
–奇数型:以s[i]为中心,向两边延伸判断
–偶数型:以s[i]和s[i+1]为起点分别延伸
每次判断完后,记录子串

代码

char* longestPalindrome(char* s) {
    char *a=(char *)malloc(sizeof(char)*1001);//开辟空间
    int i,j,k,max = 0;
    for(i=0;i<strlen(s);i++)
    {
        j=0;
        while(s[i-j] == s[i+j] && i-j>=0 && i+j < strlen(s))//奇数型
        {
            j++;
        }
        if(j*2-1 > max)
        {
            max = j*2 - 1;
            for(k=0;k<j*2-1;k++)
            {
                a[k]=s[k+i-j+1];
            }
            a[k]='\0';
        }
        j=0;
        while(s[i-j] == s[i+j+1] && i-j>=0 && i+j+1<strlen(s))//偶数型
        {
            j++;
        }
        if(j*2 > max)
        {
            max = j*2;
            for(k=0;k<j*2;k++)
            {
                a[k]=s[k+i-j+1];
            }
            a[k]='\0';
        }
    }
    return a;
}
如果本文对你有用,可以请作者喝杯茶~
0%