首页 > itarticle > leetcode 第5题 longest palindromic substring

leetcode 第5题 longest palindromic substring

admin 11月 14, 2020 0

题目地址

https://leetcode.com/problems/longest-palindromic-substring/description/

题目描述

/*
 * @lc app=leetcode id=5 lang=c
 *
 * [5] Longest Palindromic Substring
 *
 * https://leetcode.com/problems/longest-palindromic-substring/description/
 *
 * algorithms
 * Medium (27.35%)
 * Total Accepted:    566K
 * Total Submissions: 2.1M
 * Testcase Example:  '"babad"'
 *
 * Given a string s, find the longest palindromic substring in s. You may
 * assume that the maximum length of s is 1000.
 *
 * Example 1:
 *
 *
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 *
 *
 * Example 2:
 *
 *
 * Input: "cbbd"
 * Output: "bb"
 *
 *
 */


char * longestPalindrome(char * s){

}

思路

这道题求最长回文子串,首先需要了解回文字符串,回文字符串就是正着读和反着读都是一样的字符串,例如: xyzazyx, 小兔小.
可以遍历字符串,从中间向两端扩展法判断是否是回文字符串.即判断s[i-1] == s[j+1]是否相同,如果相同则 i - - (左移一位),
j++(右移一位);当不相同时,判断j-i+1 和已知的最长回文子串的大小,并保存相应的回文子串的起始位置.

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* longestPalindrome(char* s) {
    if(!s[0])
        return s;
    int length = strlen(s);
    int max_length = 1;
    int max_i = 0;
    int k = 0;

    while(k<length)
    {
        int i=k;
        int j=k;
        while(j<length-1 && s[j] == s[j+1]) j++;
        k = j+1;
        while(j<length-1 && i>0 && s[i-1] == s[j+1])
        {
            j++;
            i--;
        }
        if(j-i+1 >= max_length)
        {
            max_length = j-i+1;
            max_i = i;
        }
    }

    char* p = (char *)malloc((max_length+1)*sizeof(char));
    memcpy(p, &s[max_i], max_length);
    p[max_length] = '