用pytho代码实现假设有两个字符串s1和s2,计算通过增添、删除、替换三种操作后,从s1转变为s2所需要的操作次数。
时间: 2024-05-09 11:20:30 浏览: 135
可以使用动态规划算法来解决这个问题。
首先,我们定义一个二维数组dp,其中dp[i][j]表示将s1的前i个字符转换为s2的前j个字符所需的最小操作次数。
接着,我们可以根据s1和s2的字符来进行状态转移:
如果s1[i] == s2[j],那么dp[i][j] = dp[i-1][j-1],即不需要进行任何操作。
如果s1[i] != s2[j],那么我们可以进行以下三种操作:
增添操作:dp[i][j] = dp[i][j-1] + 1,表示将s2[j]插入到s1[i]之后,操作次数加1。
删除操作:dp[i][j] = dp[i-1][j] + 1,表示将s1[i]删除,操作次数加1。
替换操作:dp[i][j] = dp[i-1][j-1] + 1,表示将s1[i]替换为s2[j],操作次数加1。
最后,dp[-1][-1]就是将s1转换为s2所需的最小操作次数。
下面是实现代码:
```python
def minDistance(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
# 初始化dp数组
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 s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
return dp[-1][-1]
```
测试代码:
```python
s1 = "horse"
s2 = "ros"
print(minDistance(s1, s2)) # 输出3,即将"horse"转换为"ros"需要三次操作
s1 = "intention"
s2 = "execution"
print(minDistance(s1, s2)) # 输出5,即将"intention"转换为"execution"需要五次操作
```
阅读全文