Better edit distance

edit.py

from typing import Any, Sequence

import numpy


def _edit_distance(x: Sequence[Any], y: Sequence[Any]) -> int:
    idim = len(x) + 1
    jdim = len(y) + 1
    table = numpy.empty((idim, jdim), dtype=numpy.uint16)
    table[:, 0] = range(idim)
    table[0, :] = range(jdim)
    for i in range(1, idim):
        for j in range(1, jdim):
            if x[i - 1] == y[j - 1]:
                table[i][j] = table[i - 1][j - 1]
            else:
                c1 = table[i - 1][j]
                c2 = table[i][j - 1]
                c3 = table[i - 1][j - 1]
                table[i][j] = min(c1, c2, c3) + 1
    return int(table[-1][-1])


assert _edit_distance("nana", "banana") == 2
assert _edit_distance("banana", "nana") == 2