Distancia de edición (Levenshtein)

def tabla(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            dp[i][j] = dp[i - 1][j - 1] if a[i - 1] == b[j - 1] else 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    return dp


def operaciones(a, b, dp):
    """Vuelve desde la esquina eligiendo de qué casilla salió cada valor: así salen las operaciones."""
    ops = []
    i, j = len(a), len(b)
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1] and dp[i][j] == dp[i - 1][j - 1]:
            i -= 1
            j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.insert(0, a[i - 1] + "→" + b[j - 1])    # sustituir
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.insert(0, "-" + a[i - 1])               # borrar
            i -= 1
        else:
            ops.insert(0, "+" + b[j - 1])               # insertar
            j -= 1
    return ops


for x, y in [("casa", "cesta"), ("gato", "pato"), ("kitten", "sitting"), ("algoritmo", "logaritmo")]:
    dp = tabla(x, y)
    print(f"{x} → {y}: {dp[len(x)][len(y)]} ({', '.join(operaciones(x, y, dp))})")

function tabla(a, b) {
    const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
    for (let i = 0; i <= a.length; i++) dp[i][0] = i;
    for (let j = 0; j <= b.length; j++) dp[0][j] = j;
    for (let i = 1; i <= a.length; i++)
        for (let j = 1; j <= b.length; j++)
            dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1]
                : 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
    return dp;
}

/** Vuelve desde la esquina eligiendo de qué casilla salió cada valor: así salen las operaciones. */
function operaciones(a, b, dp) {
    const ops = [];
    let i = a.length, j = b.length;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i - 1] === b[j - 1] && dp[i][j] === dp[i - 1][j - 1]) {
            i--;
            j--;
        } else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {
            ops.unshift(a[i - 1] + "→" + b[j - 1]);    // sustituir
            i--;
            j--;
        } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
            ops.unshift("-" + a[i - 1]);                // borrar
            i--;
        } else {
            ops.unshift("+" + b[j - 1]);                // insertar
            j--;
        }
    }
    return ops;
}

for (const [x, y] of [["casa", "cesta"], ["gato", "pato"], ["kitten", "sitting"], ["algoritmo", "logaritmo"]]) {
    const dp = tabla(x, y);
    console.log(`${x} → ${y}: ${dp[x.length][y.length]} (${operaciones(x, y, dp).join(", ")})`);
}

using System;
using System.Collections.Generic;

class Program {
    static int[,] Tabla(string a, string b) {
        int[,] dp = new int[a.Length + 1, b.Length + 1];
        for (int i = 0; i <= a.Length; i++) dp[i, 0] = i;
        for (int j = 0; j <= b.Length; j++) dp[0, j] = j;
        for (int i = 1; i <= a.Length; i++)
            for (int j = 1; j <= b.Length; j++)
                dp[i, j] = a[i - 1] == b[j - 1] ? dp[i - 1, j - 1]
                        : 1 + Math.Min(dp[i - 1, j - 1], Math.Min(dp[i - 1, j], dp[i, j - 1]));
        return dp;
    }

    /// Vuelve desde la esquina eligiendo de qué casilla salió cada valor: así salen las operaciones.
    static List<string> Operaciones(string a, string b, int[,] dp) {
        var ops = new List<string>();
        int i = a.Length, j = b.Length;
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && a[i - 1] == b[j - 1] && dp[i, j] == dp[i - 1, j - 1]) {
                i--;
                j--;
            } else if (i > 0 && j > 0 && dp[i, j] == dp[i - 1, j - 1] + 1) {
                ops.Insert(0, a[i - 1] + "→" + b[j - 1]);   // sustituir
                i--;
                j--;
            } else if (i > 0 && dp[i, j] == dp[i - 1, j] + 1) {
                ops.Insert(0, "-" + a[i - 1]);              // borrar
                i--;
            } else {
                ops.Insert(0, "+" + b[j - 1]);              // insertar
                j--;
            }
        }
        return ops;
    }

    static void Main() {
        string[][] parejas = { new[] { "casa", "cesta" }, new[] { "gato", "pato" }, new[] { "kitten", "sitting" }, new[] { "algoritmo", "logaritmo" } };
        foreach (var p in parejas) {
            int[,] dp = Tabla(p[0], p[1]);
            Console.WriteLine(p[0] + " → " + p[1] + ": " + dp[p[0].Length, p[1].Length] + " (" + string.Join(", ", Operaciones(p[0], p[1], dp)) + ")");
        }
    }
}

<?php
function tabla(string $a, string $b): array {
    $dp = array_fill(0, strlen($a) + 1, array_fill(0, strlen($b) + 1, 0));
    for ($i = 0; $i <= strlen($a); $i++) $dp[$i][0] = $i;
    for ($j = 0; $j <= strlen($b); $j++) $dp[0][$j] = $j;
    for ($i = 1; $i <= strlen($a); $i++)
        for ($j = 1; $j <= strlen($b); $j++)
            $dp[$i][$j] = $a[$i - 1] === $b[$j - 1] ? $dp[$i - 1][$j - 1]
                : 1 + min($dp[$i - 1][$j - 1], $dp[$i - 1][$j], $dp[$i][$j - 1]);
    return $dp;
}

/** Vuelve desde la esquina eligiendo de qué casilla salió cada valor: así salen las operaciones. */
function operaciones(string $a, string $b, array $dp): array {
    $ops = [];
    $i = strlen($a);
    $j = strlen($b);
    while ($i > 0 || $j > 0) {
        if ($i > 0 && $j > 0 && $a[$i - 1] === $b[$j - 1] && $dp[$i][$j] == $dp[$i - 1][$j - 1]) {
            $i--;
            $j--;
        } elseif ($i > 0 && $j > 0 && $dp[$i][$j] == $dp[$i - 1][$j - 1] + 1) {
            array_unshift($ops, $a[$i - 1] . "→" . $b[$j - 1]);   // sustituir
            $i--;
            $j--;
        } elseif ($i > 0 && $dp[$i][$j] == $dp[$i - 1][$j] + 1) {
            array_unshift($ops, "-" . $a[$i - 1]);                // borrar
            $i--;
        } else {
            array_unshift($ops, "+" . $b[$j - 1]);                // insertar
            $j--;
        }
    }
    return $ops;
}

foreach ([["casa", "cesta"], ["gato", "pato"], ["kitten", "sitting"], ["algoritmo", "logaritmo"]] as [$x, $y]) {
    $dp = tabla($x, $y);
    echo "$x → $y: " . $dp[strlen($x)][strlen($y)] . " (" . implode(", ", operaciones($x, $y, $dp)) . ")\n";
}

def distancia(a, b):
    """Con dos filas basta: cada fila solo necesita la anterior."""
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            cur[j] = prev[j - 1] if a[i - 1] == b[j - 1] else 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[len(b)]


diccionario = ["casa", "cosa", "caso", "clase", "programa", "algoritmo", "variable", "funcion"]
for palabra in ["progama", "algorimto", "clace", "kasa", "varaible", "zzz"]:
    mejor, d = None, float("inf")
    for w in diccionario:
        x = distancia(palabra, w)
        if x < d:                                     # con empate se queda la primera del diccionario
            d, mejor = x, w
    if d <= 2:
        print(f"{palabra} → ¿quisiste decir «{mejor}»? (distancia {d})")
    else:
        print(f"{palabra} → sin sugerencias (la más cercana está a {d})")

/** Con dos filas basta: cada fila solo necesita la anterior. */
function distancia(a, b) {
    let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
    let cur = new Array(b.length + 1).fill(0);
    for (let i = 1; i <= a.length; i++) {
        cur[0] = i;
        for (let j = 1; j <= b.length; j++)
            cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1] : 1 + Math.min(prev[j - 1], prev[j], cur[j - 1]);
        [prev, cur] = [cur, prev];
    }
    return prev[b.length];
}

const diccionario = ["casa", "cosa", "caso", "clase", "programa", "algoritmo", "variable", "funcion"];
for (const palabra of ["progama", "algorimto", "clace", "kasa", "varaible", "zzz"]) {
    let mejor = null, d = Infinity;
    for (const w of diccionario) {
        const x = distancia(palabra, w);
        if (x < d) {                                  // con empate se queda la primera del diccionario
            d = x;
            mejor = w;
        }
    }
    console.log(d <= 2 ? `${palabra} → ¿quisiste decir «${mejor}»? (distancia ${d})` : `${palabra} → sin sugerencias (la más cercana está a ${d})`);
}

using System;

class Program {
    /// Con dos filas basta: cada fila solo necesita la anterior.
    static int Distancia(string a, string b) {
        int[] prev = new int[b.Length + 1], cur = new int[b.Length + 1];
        for (int j = 0; j <= b.Length; j++) prev[j] = j;
        for (int i = 1; i <= a.Length; i++) {
            cur[0] = i;
            for (int j = 1; j <= b.Length; j++)
                cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] : 1 + Math.Min(prev[j - 1], Math.Min(prev[j], cur[j - 1]));
            (prev, cur) = (cur, prev);
        }
        return prev[b.Length];
    }

    static void Main() {
        string[] diccionario = { "casa", "cosa", "caso", "clase", "programa", "algoritmo", "variable", "funcion" };
        foreach (string palabra in new[] { "progama", "algorimto", "clace", "kasa", "varaible", "zzz" }) {
            string? mejor = null;
            int d = int.MaxValue;
            foreach (string w in diccionario) {
                int x = Distancia(palabra, w);
                if (x < d) {                                  // con empate se queda la primera del diccionario
                    d = x;
                    mejor = w;
                }
            }
            Console.WriteLine(d <= 2 ? 
quot;{palabra} → ¿quisiste decir «{mejor}»? (distancia {d})" : 
quot;{palabra} → sin sugerencias (la más cercana está a {d})");
        }
    }
}

<?php
/** Con dos filas basta: cada fila solo necesita la anterior. */
function distancia(string $a, string $b): int {
    $prev = range(0, strlen($b));
    $cur = array_fill(0, strlen($b) + 1, 0);
    for ($i = 1; $i <= strlen($a); $i++) {
        $cur[0] = $i;
        for ($j = 1; $j <= strlen($b); $j++)
            $cur[$j] = $a[$i - 1] === $b[$j - 1] ? $prev[$j - 1] : 1 + min($prev[$j - 1], $prev[$j], $cur[$j - 1]);
        [$prev, $cur] = [$cur, $prev];
    }
    return $prev[strlen($b)];
}

$diccionario = ["casa", "cosa", "caso", "clase", "programa", "algoritmo", "variable", "funcion"];
foreach (["progama", "algorimto", "clace", "kasa", "varaible", "zzz"] as $palabra) {
    $mejor = null;
    $d = PHP_INT_MAX;
    foreach ($diccionario as $w) {
        $x = distancia($palabra, $w);
        if ($x < $d) {                                // con empate se queda la primera del diccionario
            $d = $x;
            $mejor = $w;
        }
    }
    echo $d <= 2 ? "$palabra → ¿quisiste decir «{$mejor}»? (distancia $d)\n" : "$palabra → sin sugerencias (la más cercana está a $d)\n";
}