day56 | 583. 两个字符串的删除操作、72. 编辑距离

**Day56 |583.两个字符串的删除操作**

在本题中，我们需要实现一个函数来计算两个字符串之间的最小编辑距离。这个问题可以转化为动态规划的问题。

### 编辑距离定义编辑距离是指将一个字符串转换成另一个字符串所需的最少操作次数，包括插入、删除和替换。

### 动态规划解决方案我们可以使用一个二维数组来存储两个字符串之间的编辑距离。其中，`dp[i][j]` 表示第 `i` 个字符到第 `j` 个字符所需的最少操作次数。

def minDistance(word1, word2):
 m, n = len(word1), len(word2)
 # 初始化动态规划数组 dp = [[0 for _ in range(n +1)] for _ in range(m +1)]
 # 填充边界条件 for i in range(m +1):
 dp[i][0] = i for j in range(n +1):
 dp[0][j] = j # 填充动态规划数组 for i in range(1, m +1):
 for j in range(1, n +1):
 if word1[i -1] == word2[j -1]:
 dp[i][j] = dp[i -1][j -1]
 else:
 dp[i][j] =1 + min(dp[i -1][j], dp[i][j -1])
 return dp[m][n]

# 测试用例print(minDistance("horse", "ros")) # 输出:3