Calculate edit distance
Find the minimum number of single-character insertions, deletions, and replacements needed to transform one string into another.
Course progress
Problem 49 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
first = "kitten"; second = "sitting"
Expected output
3
What is happening?
Replace k with s, replace e with i, and insert g at the end. These three edits transform kitten into sitting.
Solution strategy
Build the right mental model
Build a table for all prefix pairs. Matching final characters reuse the diagonal value; otherwise add one to the best insertion, deletion, or replacement state.
Core concepts
dynamic programming · strings
Complexity
Time O(n x m), space O(n x m).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for edit-distance
using System;
class Program
{
static int EditDistance(string first, string second)
{
int[,] edits = new int[first.Length + 1, second.Length + 1];
for (int i = 0; i <= first.Length; i++) edits[i, 0] = i;
for (int j = 0; j <= second.Length; j++) edits[0, j] = j;
for (int i = 1; i <= first.Length; i++)
{
for (int j = 1; j <= second.Length; j++)
{
if (first[i - 1] == second[j - 1])
edits[i, j] = edits[i - 1, j - 1];
else
edits[i, j] = 1 + Math.Min(edits[i - 1, j - 1],
Math.Min(edits[i - 1, j], edits[i, j - 1]));
}
}
return edits[first.Length, second.Length];
}
static void Main()
{
Console.WriteLine(EditDistance("kitten", "sitting"));
}
}Knowledge check
Questions students often ask
What is the main idea behind calculate edit distance?
Build a table for all prefix pairs. Matching final characters reuse the diagonal value; otherwise add one to the best insertion, deletion, or replacement state.
What is the time and space complexity of this solution?
Time O(n x m), space O(n x m).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.