Sizing the Table Without the Empty Prefix

An m by n table has no row for nothing matched yet, so the first characters have nowhere to read from.

A sequence table sized m by n, one row per character instead of m + 1, leaves out the empty prefix, so the first row and column read from entries that do not exist. The symptom depends on the language: Java and TypeScript fail with an index error, and Python returns a number, sometimes the right one and sometimes not. This card shows the smaller table, what each language does with it, why Python's answer can be wrong without any error, and the fix.

The mistake is natural because the strings themselves have m and n characters. The listing below indexes the table by character position, from 0, and so reads row i − 1 and column j − 1 even when i or j is 0.

missing_row.pypy

def lcs_length(a: str, b: str) -> int:
    table = [[0] * len(b) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[-1][-1]


print(f"MONEY, LEMON: {lcs_length('MONEY', 'LEMON')}")
print(f"LEMON, MONEY: {lcs_length('LEMON', 'MONEY')}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

MONEY, LEMON: 3
LEMON, MONEY: 4

MONEY against LEMON gives the right length, 3, and the same two words the other way round give 4, longer than either common subsequence could be. Nothing fails. In Python, index −1 is the last element, so table[i − 1] at i = 0 reads the last row and table[i][j − 1] at j = 0 reads the last column of the row. Most of those cells still hold 0 when they are read, which is why the first call happens to come out right. The second call goes wrong when the M at the start of MONEY meets the M in the middle of LEMON: the diagonal read wraps round to the end of the row for E, which has already counted a match, and the M is counted on top of it.

The same table in the other two languages fails at the first read of index −1, which at least stops the program. The table below gives what each printed for MONEY and LEMON.

The m by n table on MONEY and LEMON in each language, from a run
Language	What happened
Python	Printed 3, and 4 for LEMON and MONEY, with no error
Java	Threw java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
TypeScript	Threw TypeError: Cannot read properties of undefined (reading '0'), because table[-1] is undefined

The cost of the Python version is a wrong answer that passes any test whose strings do not trigger the wrap, which may be all of them. The remedy is to give the empty prefix its row and column: size the table m + 1 by n + 1, loop i and j from 1, and compare a[i − 1] with b[j − 1]. Row 0 and column 0 then hold the empty prefix's answers, and every read lands inside the table.

empty_row.pypy

def lcs_length(a: str, b: str) -> int:
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[-1][-1]


print(f"MONEY, LEMON: {lcs_length('MONEY', 'LEMON')}")
print(f"LEMON, MONEY: {lcs_length('LEMON', 'MONEY')}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

MONEY, LEMON: 3
LEMON, MONEY: 3

Both orders now give 3. For edit distance the empty row and column are not zeros but 0, 1, 2 and so on, the cost of building each prefix from nothing, and they have to be filled before the loop starts.

On the Algorithms: Design Strategies cheatsheet

← → move through sections and cards