leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

longest_palindromic_substr.c (842B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 5. Longest Palindromic Substring
#include "leetcode.h"

/*
 * given a string 's', return the longest palindromic substring in 's'
 */

char *longestPalindrome(char *s) {
  char *start, *end, *p = s, *sub_start = s;
  int max_len = 1;
  while (*p) {
    start = p;
    end = p;
    while (*(end + 1) && *(end + 1) == *end)
      end++;
    p = end + 1;
    while (*(end + 1) && (start > s) && *(end + 1) == *(start - 1)) {
      start--;
      end++;
    }
    if (end - start + 1 > max_len) {
      max_len = end - start + 1;
      sub_start = start;
    }
  }
  char *ans = (char *)calloc(max_len + 1, sizeof(char));
  strncpy(ans, sub_start, max_len);
  return ans;
}

int main() {
  char s1[] = {"babad"}, s2[] = {"cbbd"};
  printf("%s\n", longestPalindrome(s1)); // expect: bab
  printf("%s\n", longestPalindrome(s2)); // expect: bb
}