Edit Distance (Levenshtein Distance)
Edit Distance, also known as Levenshtein Distance, computes the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. Named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, this fundamental algorithm has applications in spell checking, DNA sequence analysis, natural language processing, and plagiarism detection.
Visualization
Interactive visualization for Edit Distance (Levenshtein Distance)
Edit Distance (Levenshtein)
• Time: O(m × n)
• Space: O(m × n)
• Used in spell checkers, DNA analysis
Interactive visualization with step-by-step execution
Implementation
1function editDistance(str1: string, str2: string): number {
2 const m = str1.length;
3 const n = str2.length;
4 const dp: number[][] = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
5
6 for (let i = 0; i <= m; i++) dp[i][0] = i;
7 for (let j = 0; j <= n; j++) dp[0][j] = j;
8
9 for (let i = 1; i <= m; i++) {
10 for (let j = 1; j <= n; j++) {
11 if (str1[i - 1] === str2[j - 1]) {
12 dp[i][j] = dp[i - 1][j - 1];
13 } else {
14 dp[i][j] = 1 + Math.min(
15 dp[i - 1][j], // deletion
16 dp[i][j - 1], // insertion
17 dp[i - 1][j - 1] // substitution
18 );
19 }
20 }
21 }
22
23 return dp[m][n];
24}Deep Dive
Theoretical Foundation
Edit Distance uses dynamic programming with a 2D table dp[i][j] representing the minimum edits needed to transform the first i characters of string1 into the first j characters of string2. The recurrence relation is: if characters match, dp[i][j] = dp[i-1][j-1]; otherwise, dp[i][j] = 1 + min(dp[i-1][j] for deletion, dp[i][j-1] for insertion, dp[i-1][j-1] for substitution). Base cases are dp[i][0]=i (delete all i characters) and dp[0][j]=j (insert all j characters). The algorithm builds up solutions from smaller subproblems, ensuring optimal substructure. Time complexity is O(mn) and space is O(mn), though it can be optimized to O(min(m,n)) by keeping only two rows. This metric satisfies the triangle inequality and is a true metric in mathematical sense.
Complexity
Time
O(mn)
O(mn)
O(mn)
Space
O(mn)
Applications
Industry Use
Spell checkers suggesting corrections (Microsoft Word, Google Docs)
DNA sequence alignment in bioinformatics
Plagiarism detection and document similarity
Speech recognition error correction
OCR (Optical Character Recognition) post-processing
Fuzzy string matching in databases
Autocorrect and predictive text on smartphones
Version control systems (diff algorithms)
Natural language processing and machine translation
Record linkage in data integration
Use Cases
Related Algorithms
0/1 Knapsack Problem
A classic optimization problem where you must select items with given weights and values to maximize total value without exceeding the knapsack's capacity. Each item can be taken only once (0 or 1). This is a fundamental problem in combinatorial optimization, resource allocation, and decision-making scenarios.
Longest Common Subsequence (LCS)
Finds the longest subsequence common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is fundamental in diff utilities, DNA sequence analysis, and version control systems like Git.
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) finds the length of the longest subsequence in an array where all elements are in strictly increasing order. Unlike a subarray, a subsequence doesn't need to be contiguous - elements can be selected from anywhere as long as their order is preserved. This classic DP problem has two solutions: O(n²) dynamic programming and O(n log n) binary search with patience sorting. Applications include stock price analysis, scheduling, Box Stacking Problem, and Building Bridges Problem.
Coin Change Problem
The Coin Change Problem finds the minimum number of coins needed to make a given amount using unlimited supplies of given coin denominations. It's a classic example of both dynamic programming and greedy algorithms, with two main variants: finding the minimum number of coins (optimization) and counting the number of ways to make change (counting). This problem has direct applications in currency systems, vending machines, and resource optimization.