linkjobai 修订了这个 Gist 5 days ago. 转到此修订
1 file changed, 42 insertions
editdist.md(文件已创建)
| @@ -0,0 +1,42 @@ | |||
| 1 | + | # Edit Distance: A Dynamic Programming Walkthrough | |
| 2 | + | ||
| 3 | + | **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. | |
| 4 | + | ||
| 5 | + | ## Define the state | |
| 6 | + | ||
| 7 | + | `dp[i][j]` = minimum edits to turn the first `i` characters of `a` into the first `j` characters of `b`. | |
| 8 | + | ||
| 9 | + | - If `a[i-1] == b[j-1]`: `dp[i][j] = dp[i-1][j-1]`. | |
| 10 | + | - Otherwise: `1 + min(dp[i-1][j]` (delete), `dp[i][j-1]` (insert), `dp[i-1][j-1]` (replace)`)`. | |
| 11 | + | - Base cases: `dp[i][0] = i`, `dp[0][j] = j`. | |
| 12 | + | ||
| 13 | + | ```python | |
| 14 | + | def min_distance(a, b): | |
| 15 | + | prev = list(range(len(b) + 1)) | |
| 16 | + | for i in range(1, len(a) + 1): | |
| 17 | + | cur = [i] + [0] * len(b) | |
| 18 | + | for j in range(1, len(b) + 1): | |
| 19 | + | if a[i-1] == b[j-1]: | |
| 20 | + | cur[j] = prev[j-1] | |
| 21 | + | else: | |
| 22 | + | cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1]) | |
| 23 | + | prev = cur | |
| 24 | + | return prev[-1] | |
| 25 | + | ``` | |
| 26 | + | ||
| 27 | + | Time O(mn); space O(n) with the rolling row. | |
| 28 | + | ||
| 29 | + | ## How to present it | |
| 30 | + | ||
| 31 | + | 1. Start from recursion: "compare the last characters; three choices if they differ." | |
| 32 | + | 2. Point out the overlapping subproblems and add memoisation. | |
| 33 | + | 3. Convert to the bottom-up table, then compress to one row. | |
| 34 | + | ||
| 35 | + | Walking through those steps out loud is exactly what interviewers mean by "show your thought process." | |
| 36 | + | ||
| 37 | + | ## Same template, other problems | |
| 38 | + | ||
| 39 | + | Longest Common Subsequence (1143), Delete Operation for Two Strings (583), and One Edit Distance (161), which has an O(n) shortcut. | |
| 40 | + | ||
| 41 | + | --- | |
| 42 | + | *Disclosure: I help build [Linkjob AI](https://www.linkjob.ai/), an AI interview helper.* | |
上一页
下一页