Compute the minimum number of single-character edits (insert, delete, or replace) needed to turn string s into string t — the Levenshtein distance.
Two lines: the string s, then the string t.
The minimum number of edits to transform s into t.
Example 1
horse ros
3
horse → rorse → rose → ros, three edits.
Example 2
intention execution
5
Five edits are enough and necessary.
Example 3
abc abc
0
Identical strings need no edits.
Let dp[i][j] be the edit distance between the first i characters of s and the first j of t.
If the characters match, dp[i][j] = dp[i-1][j-1]; otherwise it is 1 + the minimum of the insert, delete and replace sub-problems.
Classic DP grid. dp[i][0]=i, dp[0][j]=j; dp[i][j]=dp[i-1][j-1] on a match, else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
import sys
lines = sys.stdin.read().split('\n')
a = lines[0] if len(lines) > 0 else ''
b = lines[1] if len(lines) > 1 else ''
m, n = len(a), len(b)
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 a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
print(dp[m][n])
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.