Overview
Edit Distance, also known as Levenshtein distance, measures how different two strings are by counting the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into the other. It is one of the most widely used dynamic-programming algorithms in text processing.
Like LCS, it fills a two-dimensional DP table where dp[i][j] is the edit distance between the first i characters of one string and the first j of the other. Each cell chooses the cheapest of three neighbouring subproblems, so the whole distance is computed in O(m·n) time.
How Edit Distance works
- Build an (m+1)×(n+1) DP table; initialise row 0 and column 0 to 0,1,2,… — the cost of building a string from scratch.
- For each pair (i, j), compare character i of the first string with character j of the second.
- If the characters match, carry the diagonal value down unchanged: dp[i][j] = dp[i-1][j-1] (no edit needed).
- Otherwise take 1 + the minimum of the three neighbours: delete (dp[i-1][j]), insert (dp[i][j-1]), or replace (dp[i-1][j-1]).
- The bottom-right cell is the final edit distance; a traceback reveals the exact sequence of operations.
When to use it
- Spell checkers and autocorrect, ranking candidate words by how few edits they need.
- Fuzzy search and record linkage, matching near-duplicate names or entries.
- Bioinformatics sequence alignment, where insertions and deletions model mutations.
- Natural language processing metrics such as word error rate in speech recognition.
Complexity analysis
Computing every cell of the (m+1)×(n+1) table takes O(m·n) time and O(m·n) space. Because each cell depends only on the current and previous rows, the space can be reduced to O(min(m,n)) by keeping two rows — enough to get the distance, though recovering the operation sequence then needs extra work.
Frequently asked questions
What are the three allowed operations?
Insertion, deletion, and substitution, each costing 1 in the standard Levenshtein distance. Some variants add transposition (swapping two adjacent characters) as a fourth operation.
How is Edit Distance related to Longest Common Subsequence?
Both fill an (m+1)×(n+1) DP table over two strings with the same recurrence shape. When only insertions and deletions are allowed (no substitution), the edit distance equals m + n − 2·LCS.
Can I use custom costs for each operation?
Yes. Weighted edit distance assigns different costs to insert, delete, and replace (or even per character pair); the same DP recurrence works, just replacing the fixed cost of 1 with the relevant weight.