LCS dynamic programming in Python
Fills an O(nm) table of prefix LCS lengths and traces back an optimal subsequence.
- File
lcs_dynamic_programming.py, 56 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lcs-dynamic-programming/. The authors are listed in prov/31FDB1.jsonl.
from collections.abc import Sequence
from typing import TypeVar
T = TypeVar("T")
def lcs_table(x: Sequence[T], y: Sequence[T]) -> list[list[int]]:
"""Return c with c[i][j] = length of an LCS of x[:i] and y[:j]."""
m, n = len(x), len(y)
c = [[0] * (n + 1) for _ in range(m + 1)] # @line L1, L2
for i in range(1, m + 1): # @line L3
for j in range(1, n + 1): # @line L4
if x[i - 1] == y[j - 1]: # @line L5
c[i][j] = c[i - 1][j - 1] + 1
elif c[i - 1][j] >= c[i][j - 1]: # @line L6
c[i][j] = c[i - 1][j]
else:
c[i][j] = c[i][j - 1] # @line L7
return c # @line L8
def lcs(x: Sequence[T], y: Sequence[T]) -> list[T]:
"""Return one longest common subsequence of x and y, as a list."""
c = lcs_table(x, y)
i, j = len(x), len(y) # @line L9
z: list[T] = []
while i > 0 and j > 0: # @line L10
if x[i - 1] == y[j - 1]: # @line L11
z.append(x[i - 1])
i -= 1
j -= 1
elif c[i - 1][j] >= c[i][j - 1]: # @line L12
i -= 1
else:
j -= 1 # @line L13
z.reverse()
return z # @line L14
def lcs_length(x: Sequence[T], y: Sequence[T]) -> int:
"""Return the LCS length with two rows of the table, in O(min(len)) extra space."""
if len(y) > len(x):
x, y = y, x
prev = [0] * (len(y) + 1)
for i in range(1, len(x) + 1):
cur = [0] * (len(y) + 1)
for j in range(1, len(y) + 1):
if x[i - 1] == y[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[-1]
test_lcs_dynamic_programming.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lcs-dynamic-programming/. The authors are listed in prov/31FDB1.jsonl.
import itertools
import random
from lcs_dynamic_programming import lcs, lcs_length, lcs_table
def is_subsequence(z: list, x: list) -> bool:
it = iter(x)
return all(any(a == b for b in it) for a in z)
def brute_lcs_length(x: str, y: str) -> int:
for k in range(min(len(x), len(y)), 0, -1):
for idx in itertools.combinations(range(len(x)), k):
if is_subsequence([x[i] for i in idx], list(y)):
return k
return 0
def test_example() -> None:
x, y = "ABCBDAB", "BDCABA"
assert "".join(lcs(x, y)) == "BCBA"
assert lcs_table(x, y)[7][6] == 4
assert lcs_table(x, y)[4] == [0, 1, 1, 2, 2, 3, 3]
assert lcs_length(x, y) == 4
def test_dna() -> None:
s1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"
s2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA"
assert "".join(lcs(s1, s2)) == "GTCGTCGGAAGCCGGCCGAA"
def test_edges() -> None:
assert lcs("", "") == []
assert lcs("ABC", "") == []
assert lcs("", "ABC") == []
assert lcs("ABC", "DEF") == []
assert lcs("ABC", "ABC") == list("ABC")
assert lcs([1, 2, 3], [3, 2, 1]) in ([1], [2], [3])
assert lcs_length("AAAA", "AA") == 2
def test_random_against_brute_force() -> None:
rng = random.Random(14)
for _ in range(400):
x = "".join(rng.choice("ABC") for _ in range(rng.randrange(9)))
y = "".join(rng.choice("ABC") for _ in range(rng.randrange(9)))
z = lcs(x, y)
k = brute_lcs_length(x, y)
assert len(z) == k == lcs_length(x, y) == lcs_table(x, y)[len(x)][len(y)]
assert is_subsequence(z, list(x)) and is_subsequence(z, list(y))
What the next level needs
- the tests did not run in this build