State
dp[i][j] = min ops to convert s1[0..i-1] to s2[0..j-1].
Advertisement
State
dp[i][j] = min ops to convert s1[0..i-1] to s2[0..j-1].
Advertisement
Transition
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + min(
dp[i-1][j], // delete from s1
dp[i][j-1], // insert into s1
dp[i-1][j-1] // replace
);Base cases
dp[0][j] = j (insert j chars). dp[i][0] = i (delete i chars).
Applications
Spell-check. Diff tools. DNA sequence alignment. Fuzzy string matching. Autocorrect.