关于算法: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)。
这种办法只会返回一种解，即可能有多个最长回文串，此办法只返回最先遍历到的。