刷题笔记动态规划--字符串最少修改次数
题目描述
对于字符串str1,和字符串str2,现在要求最少通过多少次操作可以将str1转变为str2.其中一次操作是对一个字符进行 添加、删除和更改。
例如:str1 = ”abcd“,str2=“bd” res=2(删除a、删除c)
解题思路
这种类似于对字符串进行操作,求最值的问题十有八九会是动归的考点。但是令人比较头疼的是状态转移方程怎么搞定。
我们规定len1=len(str1);len2 = len(str2)。我们可以创建一个len1 x len2的矩阵edit_nums来记录最少的修改次数。M(i,j)表示对于字符串str1的字串从0到i转换成str2的从0到j的子串最少的次数。
根据题目的意思,
对记录矩阵M进行初始化:
M(0,:)等于str2子串的长度和M(:,0)等于str1的子串长度,即M(0,j) = len(str2[:j]) = j
M(i,0)=i
状态转移方程:
根据题目的意思,状态转移方程应该包含三项
增加一个元素:M(i,j)= M(i,j - 1) 1
删除一个元素: M(i,j)= M(i - 1,j) 1
更改或者不更改元素:M(i,j)= M(i - 1,j - 1) flag。当str1[i] == str2[j]时,flag=0(不对新增元素进行改动).当str1[i] != str2[j]时,flag=1(对新增元素改动).
综上所述,M(i,j) = min [M(i,j - 1) 1,M(i - 1,j) 1,M(i,j)= M(i - 1,j - 1) flag]
def leastAlta(str1,str2):
len1,len2 = len(str1),len(str2)
edit_nums = []
for _ in range(len1):
nums = [0] * len2
edit_nums.append(nums)
for i in range(len1):
edit_nums[i][0] = i
for i in range(len2):
edit_nums[0][i] = i
for i in range(1,len1):
for j in range(1,len2):
if str2[j] == str1[i]:
flag = 0
else:
flag = 1
res0 = [edit_nums[i - 1][j] 1, edit_nums[i][j-1] 1,edit_nums[i - 1][j - 1] flag]
edit_nums[i][j] = min(res0)
return edit_nums[-1][-1]
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfikiig
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13