linkjobai / Edit Distance: A Dynamic Programming Walkthrough
0 polubień
0 forków
1 plików
Ostatnio aktywne 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)).
Nowsze
Starsze