当前位置：首页 > news >正文

LeeCode 5. 最长回文子串

news 2025/4/4 20:59:30

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

答案：

char* longestPalindrome(char* s) { // leeCode 5.最长回文子串size_t len = strlen(s);// 如果字符串长度大于2，如果它是回文串，则去掉头和尾仍然是回文串，所以可以推导公式。// 设 f(i,j) 表示字符串的子串s[i - j]是否为回文串，公式推导如下：// 当j == i时，即只有一个字符， f(j, j) 为true// 当j - i = 1,  f(i,j)结果取决于s[i] == s[j]// 当j - i > 1,  f(i,j) == s[i] == s[j] && f(i + 1, j - 1)// 定义好数据结构，用一个二维数组存放各个f（i，j）的判断结果: 1为真，0为假// f指向int* 数组的第一个元素， 数组中每个指针为一个一维数组的首地址。最终求f[i][j]为true时表示的最长字串。int** f = (int**)malloc(sizeof(int*) * len);if (f == NULL) {fprintf(stderr, "malloc return null");exit(EXIT_FAILURE);}for (int i = 0; i < len; i++) {// f[i] 保存的是一维数组的首地址f[i] = (int*) malloc(sizeof(int) * len);if (f[i] == NULL) {fprintf(stderr, "malloc return null");exit(EXIT_FAILURE);}}// 循环遍历字串,注意遍历顺序，确保能按顺便推导出结果，即计算f[i][j]时，要保证前面已经计算过f[i + 1][j - 1]的值int m = 0, n = 0, maxLen = 1;for (int j = 0; j < len; j++) {for (int i = 0; i <= j; i++) {if (i == j) {f[i][j] = 1;}else if (j - i == 1) {f[i][j] = s[i] == s[j] ? 1 : 0;}else {f[i][j] = (s[i] == s[j] && f[i + 1][j - 1]) ? 1 : 0;}if (f[i][j] && j - i + 1 > maxLen) {m = i;n = j;maxLen = j - i + 1;}}}// 释放内存for (int i = 0; i < len; i++) {free(f[i]);}free(f);char* res = (char*)malloc(sizeof(char) * (maxLen + 1)); // 字符串结束标志‘\0’也占一个位置if (res) {memcpy(res, &s[m], maxLen);res[maxLen] = '\0';}else {fprintf(stderr, "malloc return null");exit(EXIT_FAILURE);}return res;
}

测试代码：

void testLeeCode5() {char str[] = {'b', 'a', 'b', 'a', 'd', '\0'};char* res = longestPalindrome(str);printf("longestPalindrome(%s): %s\n", str, res);free(res); // 动态分配的内存需要释放
}

打印结果：