关于算法:5最长回文子串LeetCodeC语言

一、暴力破解

#include <stdbool.h>#include <stdlib.h>#include <stdio.h>#include <string.h>// 判断字符串是否是回文字符串int isPalindromic(char *str, int start, int end){  while (start < end)  {    if (str[start] != str[end])    {      return false;    }    start++;    end--;  }  return true;}char *findLongestPalindromic(char *str){  int len = strlen(str);  int k = 0;  if (len < 2)  {    return str;  }  // 回文字符串最小长度为1，因为任何一个字符从左往右和从右往左读都是回文的  int maxLen = 1, startIndex = 0;  // 遍历所有长度>=2的子串  for (int i = 0; i < len - 1; i++)  {    for (int j = i + 1; j < len; j++)    {      // 当新的子串长度大于maxLen时，再判断是否回文      // 如果回文，则更新maxLen，同时更新startIndex      if (j - i + 1 > maxLen && isPalindromic(str, i, j))      {        maxLen = j - i + 1;        startIndex = i;      }    }  }  // 调配存储空间，存储新字符串并返回  // 调配的时候要多调配一个空间用来存储空字符'\0'  char *palindromic = (char *)malloc((maxLen + 1) * sizeof(char));  for (int i = 0; i < maxLen; i++)  {    palindromic[i] = str[startIndex + i];  }  palindromic[maxLen] = '\0';  return palindromic;}int main(void){  int i = 0;  char str[] = "babad";  char *palind = NULL;  palind = findLongestPalindromic(str);  while (palind[i] != '\0')  {    printf("%c", palind[i]);    i++;  }}

执行用时：304 ms, 在所有 C 提交中击败了26.13%的用户
内存耗费：5.9 MB, 在所有 C 提交中击败了79.53%的用户
工夫复杂度O(n3)，空间复杂度O(n)。
这种办法只会返回一种解，即可能有多个最长回文串，此办法只返回最先遍历到的。