linkjobai / Edit Distance: A Dynamic Programming Walkthrough
0 gustos
0 bifurcaciones
1 archivos
Última actividad 5 days ago
Interview prep notes
Edit Distance: A Dynamic Programming Walkthrough
Edit Distance (LeetCode 72) asks for the minimum number of insertions, deletions and substitutions that turn one word into another. It's the textbook two-string DP and a good template for many others.
Define the state
dp[i][j] = minimum edits to turn the first i characters of a into the first j characters of b.
- If
a[i-1] == b[j-1]:dp[i][j] = dp[i-1][j-1]. - Otherwise:
1 + min(dp[i-1][j](delete),dp[i][j-1](insert),dp[i-1][j-1](replace)).
Siguiente
Anterior