[数据结构与算法]leetcode5、最长回文字串

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

题目解析：

最长回文字串有几个特点：

1、1个字符一定是回文字串；2、首尾字符相同；3、去除首尾后的字符串依旧是回文串

因此可以使用动态规划法，开辟一个二维数组，s[i][j]代表从i到j的字符串，若s[i][j]=1表示为回文串，s[i][j]=0表示非回文串，那么s[i][j] =1的条件就是s[i] = s[j] && s[i+1][j-1]=1

char * longestPalindrome(char * s){
    int len = strlen(s);
    int** stack = (int**)malloc(sizeof(int*)*len);//开辟动态规划数组
    for(int i=0;i<len;++i){
        stack[i] = (int*)malloc(sizeof(int)*len);
        memset(stack[i],0,sizeof(int)*len);
        stack[i][i] = 1;//单一字符一定是回文串
    }
    int ret=1;//最大回文串长度初始为1
    for(int i=2;i<=len;++i){//首先从长度为2的字串开始遍历
        for(int front=0,boot=front+i-1;front<len&&boot<len;++front,++boot){
            if(i==2){//长度为2的字串如果满足首尾相等则为回文串
                if(s[front]==s[boot]) {
                    stack[front][boot] = 1;
                    ret = fmax(i,ret);
                }
            }else{
                if(s[front]==s[boot]&&stack[front+1][boot-1]==1){//长度大于2的字串需要满足上面说的三个特点，才为回文串
                    stack[front][boot]=1;
                    ret = fmax(i,ret);
                }
            }
        }
    }
    char* rett = (char*)malloc(sizeof(char)*(ret+1));//用来保存返回字符的
    memset(rett,0,sizeof(char)*(ret+1));
    for(int front=0,boot=front+ret-1;front<len&&boot<len;++front,++boot){
        if(stack[front][boot]==1) {
            memcpy(rett,&s[front],sizeof(char)*ret);
            return rett;
        }
    }
    return NULL;
}

执行用时：268 ms, 在所有?C?提交中击败了22.48%的用户

内存消耗：397 MB, 在所有?C?提交中击败了5.01%的用户