levenshtein_distance - adapated from a python script

levenshtein_distance.zig

fn levenshtein_distance(s1: []const u8, s2: []const u8, allocator: mem.Allocator) !u8 {
    // ensure b is always shorter to minimize memory allocation.
    var a = s1;
    var b = s2;
    if (a.len < b.len) mem.swap([]const u8, &a, &b);

    // init base row representing distances from an empty a
    var prev_row = try std.ArrayList(u8).initCapacity(allocator, b.len + 1);
    prev_row.expandToCapacity();
    for (prev_row.items, 0..) |*e, i| e.* = @intCast(i);

    var curr_row = try std.ArrayList(u8).initCapacity(allocator, b.len + 1);
    curr_row.expandToCapacity();
    @memset(curr_row.items, 0);

    for (1..a.len + 1) |i| {
        // first cell of current row represents transforming a[:i] to an empty b
        curr_row.items[0] = @intCast(i);

        for (1..b.len + 1) |j| {
            const cost = @intFromBool(a[i - 1] != b[j - 1]);

            curr_row.items[j] = @min(
                prev_row.items[j] + 1, //        Deletion (cell directly above)
                curr_row.items[j - 1] + 1, //    Insertion (cell to the left)
                prev_row.items[j - 1] + cost, // Substitution (diagonal top-left)
            );
        }

        @memcpy(prev_row.items, curr_row.items);
    }

    return prev_row.items[b.len];
}