给定两个字符串 s1 和 s2，以及我们可以对 s1 执行的一系列操作。我们的任务找到将 s1 转换为 s2 所需的最少编辑次数（操作数）。
- 插入：在 s1 的任意索引之前或之后插入任意字符。
- 删除：删除 s1 中的一个字符。
- 替换：用其他字符替换 s1 中任意索引处的字符。
注意： 上述所有操作的代价都是相等的。
示例：
> 输入： s1 = "geek", s2 = "gesek"
> 输出： 1
> 解释： 我们可以通过在 s1 中两个连续的 ‘e‘ 之间插入一个 ‘s‘ 来将 s1 转换为 s2。
>
> 输入： s1 = "gfg", s2 = "gfg"
> 输出： 0
> 解释： 两个字符串完全相同。
>
> 输入： s1 = "abcd", s2 = "bcfe"
> 输出： 3
> 解释： 我们可以通过删除 ‘a‘，将 ‘d‘ 替换为 ‘f‘，并在末尾插入 ‘e‘ 来将 s1 转换为 s2。
在线练习此题!
编辑距离图解：
> 假设我们有 s1="GEEXSFRGEEKKS" 和 s2="GEEKSFORGEEKS"
> 现在要将 s1 转换为 s2，我们需要至少 3 步操作：
> 操作 1: 将 ‘X‘ 替换为 ‘K‘
> 操作 2: 在 ‘F‘ 和 ‘R‘ 之间插入 ‘O‘
> 操作 3: 删除倒数第二个字符，即 ‘K‘
>
> 请参考下图以更好地理解。
> !Edit-Distance-Illustration-copy.webp)
[朴素方法] 使用递归 – 时间复杂度 O(3^(m+n))，空间复杂度 O(m*n)
> 这个思路是从两个字符串的左侧或右侧开始，逐一处理所有字符。
> 让我们从字符串的右侧开始处理，对于正在遍历的每一对字符，存在两种可能性：要么它们匹配，要么它们不匹配。如果两个字符串的最后一个字符匹配，我们只需简单地递归计算字符串剩余部分的答案。当最后一个字符不匹配时，我们执行所有三种操作来使最后的字符匹配，即插入、替换和删除。然后递归计算字符串剩余部分的结果。完成这些操作后，我们将选择最小的答案并将其加 1。
>
> 下面是针对此问题的递归树，考虑了最后字符始终不匹配的情况。
> !Recursion Tree.png)
> 当字符串的最后一个字符匹配时。发起递归调用 editDistance(m-1, n-1) 来计算字符串剩余部分的答案。
>
> 当字符串的最后一个字符不匹配时。发起三个递归调用，如下所示：
>
> – 在 s1 的末尾插入 s2[n-1] : editDistance(m, n-1)
> – 将 s1[m-1] 替换为 s2[n-1] : editDistance(m-1, n-1)
> – 删除 s1[m-1] : editDistance(m-1, n)
编辑距离的递推关系：
> – 情况 1：当两个字符串的最后一个字符相同时。editDistance(s1, s2, m, n) = editDistance(s1, s2, m-1, n-1)
> – 情况 2：当最后一个字符不同时
> – editDistance(s1, s2, m, n) = 1 + Min{ editDistance(s1, s2 ,m,n-1), editDistance(s1, s2 ,m-1, n), editDistance(s1, s2 , m-1, n-1)}
编辑距离的基本情况：
> – 情况 1：当 s1 变为空字符串时，即 m=0
> – 返回 n，因为将空字符串转换为长度为 n 的 s2 需要 n 次插入操作。
> – 情况 2：当 s2 变为空字符串时，即 n=0
> – 返回 m，因为将长度为 m 的 s1 转换为空字符串需要 m 次删除操作。
C++
INLINECODE6c5341a0`INLINECODEfac91a29
[动态规划方法] 使用 DP Memoization (自顶向下) – 时间复杂度 O(mn)，空间复杂度 O(mn)
> 在上述递归方法中，存在许多重叠的子问题。请参见上面的递归树图，其中存在许多重复的子树。我们使用 Memoization 技术来避免重新计算。我们在递归函数开始时检查结果是否已经计算出来，如果是，则直接返回存储的结果。
#### 辅助空间：O(m*n) + O(m+n)
这里，O(m*n) 用于存储 dp 数组/表，O(m+n) 是递归栈空间。
C++
INLINECODEaa0f98c3`INLINECODEd15eaf7a
[动态规划方法] 使用 Tabulation (自底向上) – 时间复杂度 O(mn)，空间复杂度 O(mn)
> 我们可以创建一个二维数组 dp[m+1][n+1] 来存储子问题的解。在自底向上的方法中，我们首先解决较小的子问题，然后从中解决较大的子问题。
#### 辅助空间：O(m*n)
C++
INLINECODE4640901b`INLINECODEb00144d6
空间优化方法 – 时间复杂度 O(m*n)，空间复杂度 O(n)
> 在上面的方法中，我们只使用了前一行（INLINECODE3bd9649f）和当前行（INLINECODE0218d386）的数据来计算结果。因此，我们不需要整个二维矩阵，只需要两个一维数组来存储前一行和当前行的结果。
C++
INLINECODEf9a7a272`INLINECODEb5d5025a
进一步的空间优化（仅使用一维数组）- 时间复杂度 O(m*n)，空间复杂度 O(n)
> 我们还可以进一步优化空间，仅使用一个一维数组 INLINECODE7f5e77c1 和一个变量来存储 INLINECODEc9db59d6（对角线值）。
C++
INLINECODEd279b5ca`INLINECODE14078e12“