Introduction
Edit distance, also known as Levenshtein distance, measures how dissimilar two strings are by counting the minimum number of single-character insertions, deletions, and substitutions required to transform one string into the other. It is widely used in spell checkers, DNA sequence alignment, plagiarism detection, and fuzzy string matching (like 'did you mean' suggestions). Edit distance is a classic 2D dynamic programming problem: the state is defined over prefixes of both strings, and the recurrence branches on whether the current characters match or one of the three edit operations is applied.
Cricket analogy: Comparing two very similar batting scorecards by counting the minimum swaps, insertions, and deletions of deliveries needed to turn one over into another is exactly the edit-distance question, useful for detecting near-duplicate match logs.
Approach/Syntax
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
# dp[i][j] = min edits to convert word1[:i] into word2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # delete all i characters of word1
for j in range(n + 1):
dp[0][j] = j # insert all j characters of word2
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # characters match, no edit needed
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # delete from word1
dp[i][j - 1], # insert into word1
dp[i - 1][j - 1], # substitute
)
return dp[m][n]Explanation
dp[i][j] is defined as the minimum number of edit operations needed to transform the first i characters of word1 into the first j characters of word2. If word1[i-1] equals word2[j-1] (the current last characters match), then no new edit is needed at this position, so dp[i][j] = dp[i-1][j-1]. Otherwise, we must perform one operation and take the best of three choices: deleting the character from word1 (moving from dp[i-1][j]), inserting the character from word2 into word1 (moving from dp[i][j-1]), or substituting one character for the other (moving from dp[i-1][j-1]) — in all three cases we add 1 for the operation performed. The base cases dp[i][0] = i and dp[0][j] = j handle transforming a string into or from the empty string, which requires deleting or inserting every remaining character respectively. The final answer is dp[m][n], the edit distance between the full strings.
Cricket analogy: Building up dp[i][j] as the minimum edits to turn the first i deliveries of one over-by-over log into the first j of another works ball by ball: matching deliveries cost nothing, while a mismatch forces the cheapest of removing, adding, or replacing a delivery.
Example
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
if __name__ == "__main__":
# Transform 'horse' into 'ros'
word1, word2 = "horse", "ros"
# Trace: h-o-r-s-e -> r-o-r-s-e (sub h->r) -> ro-r-s-e (del o) -> ros-e (del r... )
# Known optimal path: horse -> rorse (replace h with r) -> rose (remove r) -> ros (remove e) = 3 edits
print(edit_distance(word1, word2)) # 3Complexity
The algorithm fills an (m+1) x (n+1) table, where m and n are the lengths of the two strings, so both time and space complexity are O(m*n). Space can be optimized to O(min(m, n)) by only keeping the previous and current rows, since each cell only depends on the row directly above and the current row's previous column. This rolling-array optimization is a common technique for 2D DP problems when only the final numeric answer (not the full traceback) is needed.
Cricket analogy: Comparing two full innings scorecards fills an (m+1) x (n+1) grid of deliveries, giving O(m*n) time and space, but if only the final edit count matters, keeping just the previous and current over's row cuts space to O(min(m,n)).
Key Takeaways
- dp[i][j] = minimum edits to convert word1[:i] into word2[:j].
- If characters match, dp[i][j] = dp[i-1][j-1] with no extra cost; otherwise dp[i][j] = 1 + min(delete, insert, substitute).
- Base cases dp[i][0]=i and dp[0][j]=j handle transforming to/from the empty string.
- Time and space complexity are O(m*n); space can be reduced to O(min(m,n)) with a rolling array.
- Edit distance underlies spell checkers, DNA alignment, and fuzzy matching applications.
Practice what you learned
1. What does dp[i][j] represent in the Edit Distance DP table?
2. When word1[i-1] == word2[j-1], what is dp[i][j]?
3. What is the time complexity of the standard tabulated edit distance algorithm?
4. What do the three terms in the min() expression correspond to when characters differ?
Was this page helpful?
You May Also Like
Longest Common Subsequence
Master the LCS DP recurrence for finding the longest shared subsequence between two strings in O(mn) time.
Longest Palindromic Substring
Find the longest substring that reads the same forwards and backwards using the expand-around-center technique.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.