implementation of the levenshtein distance in python param firstword the first word to measure the difference param secondword the second word to measure the difference return the levenshtein distance between the two words examples levenshteindistanceplanet planetary 3 levenshteindistance test 4 levenshteindistancebook back 2 levenshteindistancebook book 0 levenshteindistancetest 4 levenshteindistance 0 levenshteindistanceorchestration container 10 the longer word should come first calculate insertions deletions and substitutions get the minimum to append to the current row store the previous row returns the last element distance compute the levenshtein distance between two words strings the function is optimized for efficiency by modifying rows in place param firstword the first word to measure the difference param secondword the second word to measure the difference return the levenshtein distance between the two words examples levenshteindistanceoptimizedplanet planetary 3 levenshteindistanceoptimized test 4 levenshteindistanceoptimizedbook back 2 levenshteindistanceoptimizedbook book 0 levenshteindistanceoptimizedtest 4 levenshteindistanceoptimized 0 levenshteindistanceoptimizedorchestration container 10 benchmark the levenshtein distance function param str the name of the function being benchmarked param func the function to be benchmarked get user input for words calculate and print levenshtein distances benchmark the levenshtein distance functions implementation of the levenshtein distance in python param first_word the first word to measure the difference param second_word the second word to measure the difference return the levenshtein distance between the two words examples levenshtein_distance planet planetary 3 levenshtein_distance test 4 levenshtein_distance book back 2 levenshtein_distance book book 0 levenshtein_distance test 4 levenshtein_distance 0 levenshtein_distance orchestration container 10 the longer word should come first calculate insertions deletions and substitutions get the minimum to append to the current row store the previous row returns the last element distance compute the levenshtein distance between two words strings the function is optimized for efficiency by modifying rows in place param first_word the first word to measure the difference param second_word the second word to measure the difference return the levenshtein distance between the two words examples levenshtein_distance_optimized planet planetary 3 levenshtein_distance_optimized test 4 levenshtein_distance_optimized book back 2 levenshtein_distance_optimized book book 0 levenshtein_distance_optimized test 4 levenshtein_distance_optimized 0 levenshtein_distance_optimized orchestration container 10 benchmark the levenshtein distance function param str the name of the function being benchmarked param func the function to be benchmarked get user input for words calculate and print levenshtein distances benchmark the levenshtein distance functions
from collections.abc import Callable


def levenshtein_distance(first_word: str, second_word: str) -> int:
    
    
    if len(first_word) < len(second_word):
        return levenshtein_distance(second_word, first_word)

    if len(second_word) == 0:
        return len(first_word)

    previous_row = list(range(len(second_word) + 1))

    for i, c1 in enumerate(first_word):
        current_row = [i + 1]

        for j, c2 in enumerate(second_word):
            
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)

            
            current_row.append(min(insertions, deletions, substitutions))

        
        previous_row = current_row

    
    return previous_row[-1]


def levenshtein_distance_optimized(first_word: str, second_word: str) -> int:
    
    if len(first_word) < len(second_word):
        return levenshtein_distance_optimized(second_word, first_word)

    if len(second_word) == 0:
        return len(first_word)

    previous_row = list(range(len(second_word) + 1))

    for i, c1 in enumerate(first_word):
        current_row = [i + 1] + [0] * len(second_word)

        for j, c2 in enumerate(second_word):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row[j + 1] = min(insertions, deletions, substitutions)

        previous_row = current_row

    return previous_row[-1]


def benchmark_levenshtein_distance(func: Callable) -> None:
    
    from timeit import timeit

    stmt = f"{func.__name__}('sitting', 'kitten')"
    setup = f"from __main__ import {func.__name__}"
    number = 25_000
    result = timeit(stmt=stmt, setup=setup, number=number)
    print(f"{func.__name__:<30} finished {number:,} runs in {result:.5f} seconds")


if __name__ == "__main__":
    
    first_word = input("Enter the first word for Levenshtein distance:\n").strip()
    second_word = input("Enter the second word for Levenshtein distance:\n").strip()

    
    print(f"{levenshtein_distance(first_word, second_word) = }")
    print(f"{levenshtein_distance_optimized(first_word, second_word) = }")

    
    benchmark_levenshtein_distance(levenshtein_distance)
    benchmark_levenshtein_distance(levenshtein_distance_optimized)