Basic example
Input
edit_distance("kitten", "sitting")
Output
3
Transform 'kitten' -> 'sitten' (sub k->s), 'sitten'->'sittin' (sub e->i), 'sittin'->'sitting' (insert g): 3 edits.
Full lesson preview
Compute edit distance (basic)
Calculate the minimum number of edit operations (insertions, deletions, substitutions) to convert one string into another using dynamic programming.
Python practice16 minDynamic ProgrammingIntermediateLast updated March 29, 2026
Problem statement
Given two strings s and t, compute the minimum number of single-character edits (insertions, deletions, or substitutions) required to change s into t. Implement a dynamic programming solution that builds a table of distances between all prefixes of s and t and returns the final edit distance.
Task
Implement the Levenshtein edit distance algorithm via dynamic programming (tabulation).
Examples
Input format
Two strings passed as arguments to function edit_distance(s, t).
Output format
An integer representing the minimum edit distance between s and t.
Constraints
0 <= len(s), len(t) <= 2000. Aim for O(len(s) * len(t)) time and O(min(len(s), len(t))) or O(len(s)*len(t)) space.
Samples
Sample 1
Input
edit_distance("horse", "ros")
Output
3
One possible sequence: horse -> rorse (sub h->r), rorse -> rose (del r), rose -> ros (del e) = 3