代码随想录训练营day56, 两个字符串的删除操作, 编辑字符
admin
2024-03-24 00:32:50
0次

两个字符串的删除操作

动态规划1

  1. 数组含义: 以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数

  2. 递推公式:

    1. 当两个不相等(有三种情况)

      1. 删word[i-1], 操作次数为dp[i-1][j] + 1
      2. 删word[j-1], 操作次数为dp[i][j-1] + 1
      3. 同时删两个, 操作次数为dp[i-1][j-1] + 2 (dp[i-1][j-1] + 1等于上面either, 可忽略)

      (最后当然是取最小值)

  3. 初始化: 当一个字符串是空的时, 需要几步才能变成相同的呢, 答案是i或者j

class Solution {public int minDistance(String word1, String word2) {//动规一, 通过取删除操作的最小值int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 2];//初始化, 都是i//这里是<=, 因为要让数组正好等于string长度for(int i = 0; i <= len1; i++){dp[i][0] = i;}for(int j = 0; j <= len2; j++){dp[0][j] = j;}//开始遍历for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){//如果相等的话又不用操作if(word1.charAt(i - 1) == word2.charAt(j - 1)){dp[i][j] = dp[i - 1][j - 1];} else {//不相等, 要么删i要么删j, 最小值dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[len1][len2];}
}

动态规划2:

本题基础上和LC1143(最长公共子序列)是有点相似的, 只需要算出总共相同的字母长度, 然后全部的减去这个值就行了

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];//这个版本的话先求最长公共子序列, 初始值必然是0for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){//如果相等长度就加一dp[i][j] = dp[i-1][j-1] + 1;} else {//否则分别退一步,看哪个大dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}//最后算出来的是长度, 所以两个加起来减去长度*2return len1 + len2 - dp[len1][len2]*2;}
}

编辑字符

给你两个word, 请计算出将word1转换成word2所使用的最小操作数(上一题只需要删除, 这里可以进行插入, 删除, 和替换)

仍然还是经典五部曲:

  1. 数组定义: 以i-1和j-1为结尾的数据,最近编辑距离为dp[i][j]
  2. 递推公式: 有四种操作: 不操作,增, 删, 改
    1. 如果word相等, 说明不用编辑, 那么就是dp[i-1][j-1]
    2. 如果不相等, 此时就要编辑栏
      1. 删除: word1或者word2删除一个元素, 次数加一: dp[i][j-1]+1/dp[i-1][j]+1
      2. 增加: 其实可以发现, 增加一个元素就是相当于另一个word减少一个元素
      3. 替换: 可以理解为两个都退一步, dp[i-1][j-1] + 1
  3. 初始化: 这里和上一题一样 ,默认为i
class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for(int i = 0; i <= len1; i++){dp[i][0] = i;}for(int j = 0; j <= len2; j++){dp[0][j] = j;}for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(word1.charAt(i - 1) == word2.charAt(j - 1)){//相等则不做任何操作dp[i][j] = dp[i - 1][j - 1];} else {//不相等则做, 删除和替换的操作dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1),dp[i-1][j-1] + 1);}}}return dp[len1][len2];}
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...