Plus longue sous-sequence commune (LCS)

La LCS (Longest Common Subsequence) est un problème fondamental en informatique. On l'utilise par exemple pour comparer des fichiers (comme git diff) ou des sequences ADN.

Une sous-sequence, ce n'est pas la meme chose qu'une sous-chaine. Les caracteres n'ont pas besoin d'etre contigus, juste dans le meme ordre. Par exemple, dans 'ABCDE', 'ACE' est une sous-sequence (on a garde A, C, E dans l'ordre).

On construit une matrice dp ou dp[i][j] contient la longueur de la LCS entre les i premiers caracteres de s1 et les j premiers de s2.

Si les caracteres courants sont egaux, on etend la LCS précédente de 1. Sinon, on prend le meilleur des deux sous-problèmes.

Exemples :
lcs('ABCBDAB', 'BDCAB') renvoie 4 (par exemple BCAB)
lcs('abc', 'abc') renvoie 3
lcs('abc', 'xyz') renvoie 0

Écris une fonction lcs(s1, s2) qui retourne la longueur de la plus longue sous-sequence commune.

Tests (2/4)

Exemple classique

assert lcs('ABCBDAB', 'BDCAB') == 4

Chaines identiques

assert lcs('abc', 'abc') == 3

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

← Rendu de monnaie (Coin Change) Problème du sac a dos … →

solution.py

Bravo!

Plus longue sous-sequence commune (LCS)

Tests (2/4)

Indices (3 disponibles)

Solution officielle