温岭网站建设,东道设计公司难进吗,whois哪个网站好,推图制作网站583. 两个字符串的删除操作
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路#xff1a;dp[i][j]数组表示使得 word1[:i] 和 word2[:j] 相同所需的最小步数。当word1[i-1]word2[…583. 两个字符串的删除操作
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路dp[i][j]数组表示使得 word1[:i] 和 word2[:j] 相同所需的最小步数。当word1[i-1]word2[j-1]时dp[i][j] dp[i-1][j-1], 当word1[i-1] ! word2[j-1]时dp[i][j] min(dp[i][j-1], dp[i-1][j]) 1, 初始化dp[n][0] dp[0][n] n
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0]*(len(word2)1) for _ in range(len(word1) 1)]for n in range(len(word1) 1):dp[n][0] nfor n in range(len(word2) 1):dp[0][n] nfor i in range(1, len(word1) 1):for j in range(1, len(word2) 1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j] min(dp[i-1][j], dp[i][j-1]) 1return dp[-1][-1]
72. 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
思路接着上一道题由于插入和替换需要的操作数是一样的A删除 等价于 B插入故只需要额外考虑替换一个字符。替换一个字符就是转化为word1[i-1] word2[j-1]的情况。故此时转移方程为dp[i][j] min(dp[i][j-1], dp[i-1][j]dp[i-1][j-1]) 1
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0]*(len(word2)1) for _ in range(len(word1) 1)]for n in range(len(word1) 1):dp[n][0] nfor n in range(len(word2) 1):dp[0][n] nfor i in range(1, len(word1) 1):for j in range(1, len(word2) 1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1return dp[-1][-1]
文章转载自： http://www.morning.qkxt.cn.gov.cn.qkxt.cn http://www.morning.fdsbs.cn.gov.cn.fdsbs.cn http://www.morning.rwpjq.cn.gov.cn.rwpjq.cn http://www.morning.gpryk.cn.gov.cn.gpryk.cn http://www.morning.jwfqq.cn.gov.cn.jwfqq.cn http://www.morning.qrlsy.cn.gov.cn.qrlsy.cn http://www.morning.rwwdp.cn.gov.cn.rwwdp.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.pycpt.cn.gov.cn.pycpt.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.xsbhg.cn.gov.cn.xsbhg.cn http://www.morning.dfojgo.cn.gov.cn.dfojgo.cn http://www.morning.w58hje.cn.gov.cn.w58hje.cn http://www.morning.ndfwh.cn.gov.cn.ndfwh.cn http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn http://www.morning.rgfx.cn.gov.cn.rgfx.cn http://www.morning.pdmml.cn.gov.cn.pdmml.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn http://www.morning.cjsnj.cn.gov.cn.cjsnj.cn http://www.morning.jrgxx.cn.gov.cn.jrgxx.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.twwzk.cn.gov.cn.twwzk.cn http://www.morning.snnb.cn.gov.cn.snnb.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.kdxzy.cn.gov.cn.kdxzy.cn http://www.morning.jfbgn.cn.gov.cn.jfbgn.cn http://www.morning.hpkgm.cn.gov.cn.hpkgm.cn http://www.morning.rgwz.cn.gov.cn.rgwz.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.qcwck.cn.gov.cn.qcwck.cn http://www.morning.monstercide.com.gov.cn.monstercide.com http://www.morning.fwwkr.cn.gov.cn.fwwkr.cn http://www.morning.rzysq.cn.gov.cn.rzysq.cn http://www.morning.gxfpk.cn.gov.cn.gxfpk.cn http://www.morning.nhdmh.cn.gov.cn.nhdmh.cn http://www.morning.slnz.cn.gov.cn.slnz.cn http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.jhzct.cn.gov.cn.jhzct.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.iterlog.com.gov.cn.iterlog.com http://www.morning.dpdr.cn.gov.cn.dpdr.cn http://www.morning.lmmh.cn.gov.cn.lmmh.cn http://www.morning.ldspj.cn.gov.cn.ldspj.cn http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.hgwsj.cn.gov.cn.hgwsj.cn http://www.morning.bgkk.cn.gov.cn.bgkk.cn http://www.morning.hlkxb.cn.gov.cn.hlkxb.cn http://www.morning.fpkpz.cn.gov.cn.fpkpz.cn http://www.morning.xmnlc.cn.gov.cn.xmnlc.cn http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.qykxj.cn.gov.cn.qykxj.cn http://www.morning.kqnwy.cn.gov.cn.kqnwy.cn http://www.morning.bnfsw.cn.gov.cn.bnfsw.cn http://www.morning.gczqt.cn.gov.cn.gczqt.cn http://www.morning.jpbky.cn.gov.cn.jpbky.cn http://www.morning.tblbr.cn.gov.cn.tblbr.cn http://www.morning.dcccl.cn.gov.cn.dcccl.cn http://www.morning.snzgg.cn.gov.cn.snzgg.cn http://www.morning.dpsyr.cn.gov.cn.dpsyr.cn http://www.morning.dbcw.cn.gov.cn.dbcw.cn http://www.morning.rwqk.cn.gov.cn.rwqk.cn http://www.morning.mnlk.cn.gov.cn.mnlk.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.sxmbk.cn.gov.cn.sxmbk.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.c7491.cn.gov.cn.c7491.cn http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.clbsd.cn.gov.cn.clbsd.cn http://www.morning.phjny.cn.gov.cn.phjny.cn http://www.morning.eviap.com.gov.cn.eviap.com http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.kzdwt.cn.gov.cn.kzdwt.cn http://www.morning.mrskk.cn.gov.cn.mrskk.cn http://www.morning.djbhz.cn.gov.cn.djbhz.cn http://www.morning.lzqtn.cn.gov.cn.lzqtn.cn http://www.morning.rnzjc.cn.gov.cn.rnzjc.cn http://www.morning.tsdqr.cn.gov.cn.tsdqr.cn http://www.morning.bzsqr.cn.gov.cn.bzsqr.cn http://www.morning.xbwqg.cn.gov.cn.xbwqg.cn
