72. 编辑距离
思路
记住操作的目的是时两个字符串相等
dp初始化 :
i代表 word1字符串0~i j代表word2字符串0~j
dp[0][j]:0代表空字符串,可以理解为空字符变成字符串需要插入字符的次数 即次数为 j
dp[i][0]: 字符串变成空字符串需要删除的次数,即次数为i
其余设置为0(也可设置成别的数字)
状态转换:
word1[i]==word2[j]:字符相等,则只需要看0i-1的字符串转换成0j-1字符串所需要的次数
word1[i]!=word2[j]:
有三种情况会使两个字符串:0i==0j,取操作次数最少的步骤即可
- 0~i-1可以弄出word1=word2,则再需要删word1[i]
2.0~j-1 可以弄出word1=word2,也就是0-i可以弄出word2 0~j-1的字符串,则此时word1需要再加一个字符才能相等
3.0~i-1 可以弄出0~j-1字符串,则word1需要再添加一个字符才能相等
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
dp=[[0]*(len(word2)+1) for i in range(len(word1)+1)]
#空串变成非空串,只需执行插入操作
for i in range(len(dp)):
for j in range(len(dp[0])):
if i ==0:
dp[i][j]=j
elif j==0:
dp[i][j]=i
for i in range(len(word1)):
for j in range(len(word2)):
if word1[i]==word2[j]:
#字符相等,则只需要看0~i-1的字符串转换成0~j-1字符串所需要的次数
dp[i+1][j+1]=dp[i][j]
else:
'''
1. 0~i-1可以弄出word1=word2,则再需要删word1[i]
2.0~j-1 可以弄出word1=word2,也就是0-i可以弄出word2 0~j-1的字符串,则此时word1需要再加一个字符才能相等
3.0~i-1 可以弄出0~j-1字符串,则word1需要再添加一个字符才能相等
'''
dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j],dp[i][j])+1
return dp[-1][-1]
原文地址:https://blog.csdn.net/huanxianxianshi/article/details/142799941
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!