欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 教育 > 高考 > 5. 最长回文子串

5. 最长回文子串

2025/5/9 6:03:31 来源:https://blog.csdn.net/qq_35085273/article/details/139534518  浏览:    关键词:5. 最长回文子串

题目

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

示例 1:

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

示例 2:

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

提示:

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

代码

完整代码

#include <string.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>bool isHuiwen(char* head, char* tail)
{while (head < tail){if((*head) != (*tail)){return false;}head++;tail--;}return true;
}char* longestPalindrome(char* s) {int len = strlen(s);if(len == 1){return s;}char* head = s,*tail = s + (len - 1);char* res = (char*)calloc(len + 1, sizeof(char));while(head < s + len - 1){while(head != tail){if(isHuiwen(head, tail)){if(tail-head+1 > strlen(res)){strncpy(res, head, tail-head+1);}}tail--;}tail = s + (len - 1);head++;}if(strlen(res) == 0){strncpy(res, s, 1);}return res;
}// int main(void)
// {
//     char a[] = "bb";
//     printf("return %s",longestPalindrome(a));
// }

思路分析

  1. 检查回文:定义一个函数 isHuiwen 来检查字符串 s 的子串是否为回文。
  2. 遍历字符串:使用两个指针 headtail 来遍历字符串的所有子串。
  3. 记录最长回文子串:每次找到一个回文子串时,比较其长度并记录最长的那个。

拆解分析

  • 检查回文:通过两个指针从字符串的两端向中间移动,检查字符是否相同。
  • 遍历字符串:从字符串的每一个起点开始,检查从当前起点到终点的所有子串。
  • 记录结果:每次发现新的回文子串,如果其长度大于当前记录的最长回文子串的长度,则更新结果。

复杂度分析

  • 时间复杂度O(n^3),其中 n 是字符串的长度。遍历所有子串需要 O(n^2),每次检查回文需要 O(n)
  • 空间复杂度O(n),需要额外的空间来存储最长回文子串。

结果

O(n^3)恐怖如斯
在这里插入图片描述

一题多解

动态规划

动态规划思路分析

  1. 定义状态:使用二维数组 dp,其中 dp[i][j] 表示子串 s[i...j] 是否为回文。
  2. 状态转移:如果 s[i] == s[j]dp[i+1][j-1] 为真,则 dp[i][j] 为真。
  3. 初始化:所有单个字符都是回文,即 dp[i][i] = true
  4. 结果更新:在遍历过程中记录最长的回文子串。

动态规划复杂度分析

  • 时间复杂度O(n^2),遍历所有子串。
  • 空间复杂度O(n^2),使用二维数组存储结果。

动态规划代码

char* longestPalindrome(char* s) {int len = strlen(s);if (len < 2) {return s;}int maxLen = 1, start = 0;bool dp[1000][1000] = {false};for (int i = 0; i < len; i++) {dp[i][i] = true;}for (int j = 1; j < len; j++) {for (int i = 0; i < j; i++) {if (s[i] == s[j]) {if (j - i == 1) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}} else {dp[i][j] = false;}if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;start = i;}}}char* res = (char*)malloc((maxLen + 1) * sizeof(char));strncpy(res, &s[start], maxLen);res[maxLen] = '\0';return res;
}

结果

在这里插入图片描述

中心扩展法

中心扩展法思路分析

  1. 中心扩展:从字符串的每个字符和每两个字符之间作为中心,向两边扩展寻找回文子串。
  2. 记录结果:在扩展过程中记录最长的回文子串。

中心扩展法复杂度分析

  • 时间复杂度O(n^2),每个字符都需要进行扩展。
  • 空间复杂度O(1),只使用常数级别的额外空间。

中心扩展法代码

char* longestPalindrome(char* s) {int len = strlen(s);if (len < 2) {return s;}int maxLen = 1, start = 0;for (int i = 0; i < len; i++) {int l = i, r = i;while (l >= 0 && r < len && s[l] == s[r]) {if (r - l + 1 > maxLen) {maxLen = r - l + 1;start = l;}l--;r++;}l = i, r = i + 1;while (l >= 0 && r < len && s[l] == s[r]) {if (r - l + 1 > maxLen) {maxLen = r - l + 1;start = l;}l--;r++;}}char* res = (char*)malloc((maxLen + 1) * sizeof(char));strncpy(res, &s[start], maxLen);res[maxLen] = '\0';return res;
}

结果

结果

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词