LeetCode 4

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/longest-palindromic-substring/description
Un palindrome est une chaîne qui se lit de la même façon dans les deux sens. Par exemple, "abba" est un palindrome. On cherche à trouver la plus grande sous-chaîne palindrome d'une chaîne donnée.

Indice

Un algorithme naïf qui regarde, pour tout i, j, si la sous-chaîne de s de i à j est un palindrome (= qui se lit de la même façon dans les deux sens), a une complexité O(n^3).

Pour que le programme soit accepté, on peut trouver une solution en O(n^2) par programmation dynamique. Pour cela :

1. Définir un tableau b tel que b[i][j] vaut vrai si la sous-chaîne de s de i à j est un palindrome.
2. Trouver une équation de récurrence pour b[i][j].
3. Remplir le tableau b en utilisant cette équation de récurrence.
4. Trouver la plus grande sous-chaîne palindrome en parcourant le tableau b.

On pourra utiliser la fonction suivante :

// Renvoie la sous-chaîne de s de l'indice i à j inclus
char* substring(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

Solution

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

char* subword(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);
    bool** b = malloc(n*sizeof(bool*));
    for(int i = 0; i < n; i++) {
        b[i] = malloc(n*sizeof(bool));
        for(int j = 0; j < n; j++) {
            b[i][j] = true;
        }
    }

    int imax = 0, kmax = 0;
    for(int k = 1; k < n; k++)
        for(int i = 0; i < n - k; i++) {
            b[i][i + k] = s[i] == s[i + k] && b[i + 1][i + k - 1];
            if(b[i][i + k]) {
                kmax = k;
                imax = i;
            }
        }
    return subword(s, imax, imax + kmax);
}