## Solution - ~~如果两个字符串 $s_1$ 和 $s_2$ 的长度不一样，那么 $||s_1| - |s_2||$ 个 insertion / deletion 是一定要 perform 的。我们需要做的是找到 $s_1$ 和 $s_2$ 之间的拓扑顺序上重合的最大 sequence，找到这样一个 sequence 之后，我们就可以决定去做对应的增加 / 删除操作。~~ - ~~对于这个，使用 dp，我们定义 $G[i][j] = 1$ 如果 $s_1[i] == s_2[j]$，所以这个问题就被转换成了一个 [[LeetCode 0064 - Minimum Path Sum]] 的问题，只不过你需要做的是 maximize 这个数值。~~ > [!fail] 错误原因 > 上述想法是错的是因为考虑如果两个字符串其中有两个字母重合；对于第一个字符串而言，是其前两个字母，对于第二个字符串而言，是其首尾；即：$s_1[0] = s_2[0]$，同时 $s_1[1] = s_2[n-1]$（假设 $|s_1| = m$, $|s_2| = n$）。这个就能论证错误。 - 正确答案与我一开始想的思路相似：$dp[i][j]$ 表示 $s_1[..i]$ 和 $s_2[..j]$ 之间的 edit distance。$s[..i]$ 表示 $s$ 的 $[0, i)$ 这样一左闭右开的区间。 - 考虑：$\mathtt{dp}[0][0] = 0$，且对于 $\mathtt{dp}[0][j]$ 来说，我们都可以把它赋值为 $j$；同理，对于 $\mathtt{dp}[i][0] = i$ 对于所有的 $i$ 也成立。 ## Problem ### Problem Statement Given two strings $\text{word1}$ and $\text{word2}$, return the minimum number of operations required to convert $\text{word1}$ to $\text{word2}$. You have the following three operations permitted on a word: - Insert a character - Delete a character - Replace a character ### Examples #### Example 1 **Input:** $\texttt{word1} = \text{``horse"}$, $\texttt{word2} = \text{``ros"}$ **Output:** 3 **Explanation:** $\text{horse} \rightarrow \text{rorse}$ (replace 'h' with 'r') $\text{rorse} \rightarrow \text{rose}$ (remove 'r') $\text{rose} \rightarrow \text{ros}$ (remove 'e') #### Example 2 **Input:** $\texttt{word1} = \text{``intention"}$, $\texttt{word2} = \text{``execution"}$ **Output:** 5 **Explanation:** $\text{intention} \rightarrow \text{inention}$ (remove 't') $\text{inention} \rightarrow \text{enention}$ (replace 'i' with 'e') $\text{enention} \rightarrow \text{exention}$ (replace 'n' with 'x') $\text{exention} \rightarrow \text{exection}$ (replace 'n' with 'c') $\text{exection} \rightarrow \text{execution}$ (insert 'u') ### Constraints - $0 \leq \texttt{word1.length}, \texttt{word2.length} \leq 500$ - $\texttt{word1}$ and $\texttt{word2}$ consist of lowercase English letters.