Levenshtein Distance With Two Rows

from __future__ import annotations

from collections.abc import Iterable


def levenshtein_distance(left: str, right: str) -> int:
    if not isinstance(left, str) or not isinstance(right, str):
        raise TypeError("both inputs must be strings")
    if left == right:
        return 0
    if len(left) < len(right):
        left, right = right, left
    if not right:
        return len(left)

    previous = list(range(len(right) + 1))
    for row, left_character in enumerate(left, start=1):
        current = [row]
        for column, right_character in enumerate(right, start=1):
            insertion = current[column - 1] + 1
            deletion = previous[column] + 1
            substitution = previous[column - 1] + (
                left_character != right_character
            )
            current.append(min(insertion, deletion, substitution))
        previous = current
    return previous[-1]


def similarity(left: str, right: str) -> float:
    if not isinstance(left, str) or not isinstance(right, str):
        raise TypeError("both inputs must be strings")
    longest = max(len(left), len(right))
    if longest == 0:
        return 1.0
    return 1.0 - levenshtein_distance(left, right) / longest


def closest_match(
    query: str,
    candidates: Iterable[str],
    *,
    max_distance: int | None = None,
) -> tuple[str, int] | None:
    if not isinstance(query, str):
        raise TypeError("query must be a string")
    if max_distance is not None and (
        not isinstance(max_distance, int)
        or isinstance(max_distance, bool)
        or max_distance < 0
    ):
        raise ValueError("max_distance must be a non-negative integer")

    best: tuple[str, int] | None = None
    for candidate in candidates:
        if not isinstance(candidate, str):
            raise TypeError("candidates must be strings")
        distance = levenshtein_distance(query, candidate)
        if max_distance is not None and distance > max_distance:
            continue
        if best is None or distance < best[1]:
            best = (candidate, distance)
    return best


def main() -> None:
    pairs = [
        ("kitten", "sitting"),
        ("flaw", "lawn"),
        ("", "abc"),
        ("same", "same"),
    ]
    for left, right in pairs:
        print(
            left,
            right,
            levenshtein_distance(left, right),
            round(similarity(left, right), 3),
        )

    print(closest_match("receve", ["receive", "relieve", "retrieve"]))
    print(
        closest_match(
            "receve",
            ["receive", "relieve"],
            max_distance=1,
        )
    )

    try:
        closest_match("query", ["ok", 42])
    except TypeError as error:
        print(error)


if __name__ == "__main__":
    main()