Word 1 | Word 2 | Edit Distance | Description |
---|---|---|---|
horse | ros | 3 | Replace 'h' → 'r', remove 'r', remove 'e' |
intention | execution | 5 | Requires multiple inserts, deletes, and replacements |
abc | abc | 0 | Both strings are already equal |
abc | def | 3 | All characters need to be replaced |
abcd | abc | 1 | Only one deletion is needed |
abc | abcd | 1 | Only one insertion is needed |
"" | abc | 3 | Empty word1, need 3 insertions |
abc | "" | 3 | Empty word2, need 3 deletions |
"" | "" | 0 | Both strings are empty, no operations needed |
Edit Distance Problem
Using Dynamic Programming
Topic Contents
Problem Statement
The Edit Distance problem asks: Given two strings word1
and word2
, what is the minimum number of operations required to convert word1
into word2
?
- Allowed operations are:
- Insert a character
- Delete a character
- Replace a character
- Each operation counts as 1 step.
The goal is to find the minimum number of such operations needed to make the two strings equal.
Examples
Solution
Visualization
Algorithm Steps
- Let
word1
andword2
be the input strings, with lengthsm
andn
respectively. - Create a 2D table
dp
of dimensions(m+1) x (n+1)
, wheredp[i][j]
represents the edit distance between the firsti
characters ofword1
and the firstj
characters ofword2
. - Initialize the first column: for each
i
from0
tom
, setdp[i][0] = i
(representingi
deletions). - Initialize the first row: for each
j
from0
ton
, setdp[0][j] = j
(representingj
insertions). - For each
i
from1
tom
and for eachj
from1
ton
: - If
word1[i-1]
equalsword2[j-1]
, then setdp[i][j] = dp[i-1][j-1]
. - Otherwise, set
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
. - The edit distance is
dp[m][n]
.
Code
Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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__':
print("Edit Distance between 'kitten' and 'sitting':", edit_distance("kitten", "sitting"))
print("Edit Distance between 'horse' and 'ros':", edit_distance("horse", "ros"))