data-structures · intermediate · ~15 min

Edit distance

Compute the Levenshtein distance between two strings.

Challenge

Implement:

int edit_distance(const char *a, const char *b);

Return the minimum number of single-character inserts, deletes, or substitutions to turn a into b.

Input format

Two strings.

Output format

Minimum edit operations.

Constraints

2-D table; first row/column are 0..len.

Starter code

#include <stddef.h>
/* Levenshtein edit distance (insert/delete/substitute, each cost 1) between a and b. */
int edit_distance(const char *a,const char *b){ (void)a;(void)b; return -1; }

Common mistakes

Forgetting to seed the base row and column with 0,1,2,...

Edge cases to handle

Distance to/from empty string is the other's length.

Background lessons

Solve this exercise in the browser editor — compile and run against the test harness, no setup required.