题目

给你一个字符串 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;
}

结果

结果

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部