Se X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1]
Senão: dp[i][j] = 1 + min(
    dp[i-1][j],     // remoção
    dp[i][j-1],     // inserção
    dp[i-1][j-1]    // substituição
)

X = "kitten"    Y = "sitting"

Tabela dp:
       ""  s  i  t  t  i  n  g
  ""    0  1  2  3  4  5  6  7
  k     1  1  2  3  4  5  6  7
  i     2  2  1  2  3  4  5  6
  t     3  3  2  1  2  3  4  5
  t     4  4  3  2  1  2  3  4
  e     5  5  4  3  2  2  3  4
  n     6  6  5  4  3  3  2  3

Distância = 3 (substituir k→s, substituir e→i, inserir g)

Operações:
  kitten → sitten (substituir k por s)
  sitten → sittin (substituir e por i)
  sittin → sitting (inserir g no final)

const std = @import("std");
const Allocator = std.mem.Allocator;

const Operacao = enum {
    nenhuma,
    inserir,
    remover,
    substituir,
};

const PassoEdicao = struct {
    op: Operacao,
    pos: usize,
    char_de: ?u8,
    char_para: ?u8,
};

/// Calcula a distância de edição entre duas strings.
pub fn editDistance(allocator: Allocator, x: []const u8, y: []const u8) !u32 {
    const m = x.len;
    const n = y.len;

    // Otimização de espaço: usa apenas duas linhas
    var anterior = try allocator.alloc(u32, n + 1);
    defer allocator.free(anterior);
    var atual = try allocator.alloc(u32, n + 1);
    defer allocator.free(atual);

    for (0..n + 1) |j| {
        anterior[j] = @intCast(j);
    }

    for (1..m + 1) |i| {
        atual[0] = @intCast(i);
        for (1..n + 1) |j| {
            if (x[i - 1] == y[j - 1]) {
                atual[j] = anterior[j - 1];
            } else {
                atual[j] = 1 + @min(@min(anterior[j], atual[j - 1]), anterior[j - 1]);
            }
        }
        const temp = anterior;
        anterior = atual;
        atual = temp;
    }

    return anterior[n];
}

/// Versão com reconstrução das operações.
pub fn editDistanceDetalhado(
    allocator: Allocator,
    x: []const u8,
    y: []const u8,
) !struct { distancia: u32, operacoes: []PassoEdicao } {
    const m = x.len;
    const n = y.len;

    // Tabela completa para rastreamento
    const dp = try allocator.alloc([]u32, m + 1);
    defer {
        for (dp) |row| allocator.free(row);
        allocator.free(dp);
    }

    for (0..m + 1) |i| {
        dp[i] = try allocator.alloc(u32, n + 1);
        dp[i][0] = @intCast(i);
    }
    for (0..n + 1) |j| {
        dp[0][j] = @intCast(j);
    }

    for (1..m + 1) |i| {
        for (1..n + 1) |j| {
            if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + @min(@min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
            }
        }
    }

    // Reconstrói operações
    var ops = std.ArrayList(PassoEdicao).init(allocator);
    var i: usize = m;
    var j: usize = n;
    while (i > 0 or j > 0) {
        if (i > 0 and j > 0 and x[i - 1] == y[j - 1]) {
            i -= 1;
            j -= 1;
        } else if (i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1) {
            try ops.append(.{ .op = .substituir, .pos = i - 1, .char_de = x[i - 1], .char_para = y[j - 1] });
            i -= 1;
            j -= 1;
        } else if (j > 0 and dp[i][j] == dp[i][j - 1] + 1) {
            try ops.append(.{ .op = .inserir, .pos = i, .char_de = null, .char_para = y[j - 1] });
            j -= 1;
        } else {
            try ops.append(.{ .op = .remover, .pos = i - 1, .char_de = x[i - 1], .char_para = null });
            i -= 1;
        }
    }

    return .{
        .distancia = dp[m][n],
        .operacoes = try ops.toOwnedSlice(),
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const pares = [_][2][]const u8{
        .{ "kitten", "sitting" },
        .{ "algoritmo", "logaritmo" },
        .{ "zig", "zag" },
        .{ "", "abc" },
    };

    for (pares) |par| {
        const dist = try editDistance(allocator, par[0], par[1]);
        try stdout.print("\"{s}\" → \"{s}\" = {d} operações\n", .{ par[0], par[1], dist });
    }

    // Exemplo detalhado
    try stdout.print("\nDetalhamento \"kitten\" → \"sitting\":\n", .{});
    const detalhe = try editDistanceDetalhado(allocator, "kitten", "sitting");
    defer allocator.free(detalhe.operacoes);

    for (detalhe.operacoes) |op| {
        switch (op.op) {
            .inserir => try stdout.print("  Inserir '{c}' na posição {d}\n", .{ op.char_para.?, op.pos }),
            .remover => try stdout.print("  Remover '{c}' da posição {d}\n", .{ op.char_de.?, op.pos }),
            .substituir => try stdout.print("  Substituir '{c}' por '{c}' na posição {d}\n", .{ op.char_de.?, op.char_para.?, op.pos }),
            .nenhuma => {},
        }
    }
}