首页 > 编程语言 >算法学习day56动态规划part16-583、72

算法学习day56动态规划part16-583、72

时间:2023-06-14 23:44:37浏览次数:45  
标签:583 int part16 word1 72 word2 String

package LeetCode.DPpart16;
/**
 * 583. 两个字符串的删除操作
 * 给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以删除任意一个字符串中的一个字符。
 * */
public class DeleteOperationforTwoStrings_583 {
    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 = 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]);
                }
            }
        }

        return len1 + len2 - dp[len1][len2] * 2;
    }
}
package LeetCode.DPpart16;
/**
 * 72. 编辑距离
 *给你两个单词 word1 和 word2, 请返回将word1转换成word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作:
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * */
public class EditDistance_72 {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for (int i = 1; i <= m; i++) {
            dp[i][0] =  i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 因为dp数组有效位从1开始
                // 所以当前遍历到的字符串的位置为i-1 | j-1
                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]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

 

标签:583,int,part16,word1,72,word2,String
From: https://www.cnblogs.com/lipinbigdata/p/17481661.html

相关文章

  • 072_高等数学
    1,等价公式:......
  • ASEMI代理英飞凌TLE7244SL功率电子开关,TLE7244SL参数
    编辑-ZTLE7244SL参数描述:型号:TLE7244SL数字电源电压VDD:3.0V~5.5V模拟电源电压VDDA:4.5V~5.5V每个通道在Tj=150°C时的最大导通状态电阻RDS(ON,max):1.7Ω额定负载电流IL(nom):290mA过载关断阈值ID(OVL,max):950mA25°C时每个通道的输出泄漏电流ID(STB,max):1µA......
  • 72. 编辑距离
    给你两个单词word1和word2,请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作:插入一个字符删除一个字符替换一个字符示例1:输入:word1="horse",word2="ros"输出:3解释:horse->rorse(将'h'替换为'r')rorse->rose(删......
  • TLE7244SL-ASEMI代理英飞原装汽车芯片TLE7244SL
    编辑:llTLE7244SL-ASEMI代理英飞原装汽车芯片TLE7244SL型号:TLE7244SL品牌:Infineon(英飞凌)封装:SSOP-24-150mil类型:电源负载开关TLE7244SL特性4个输入引脚,提供灵活的PWM配置由专用引脚提供跛行回家功能(直接驾驶)用于诊断和控制的16位SPI菊花链功能也与8位SPI设备兼容数字电源电压范围......
  • TLE7244SL-ASEMI代理英飞原装汽车芯片TLE7244SL
    编辑:llTLE7244SL-ASEMI代理英飞原装汽车芯片TLE7244SL型号:TLE7244SL品牌:Infineon(英飞凌)封装:SSOP-24-150mil类型:电源负载开关TLE7244SL特性4个输入引脚,提供灵活的PWM配置由专用引脚提供跛行回家功能(直接驾驶)用于诊断和控制的16位SPI菊花链功能也与8位SPI设备兼容数字......
  • 583. 两个字符串的删除操作
    给定两个单词word1和word2,返回使得word1和word2相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。示例1:输入:word1="sea",word2="eat"输出:2解释:第一步将"sea"变为"ea",第二步将"eat"变为"ea">动态规划classSolution{p......
  • A572Gr50钢板简介、A572Gr50期货订轧、A572Gr50力学性能
    一、A572Gr50钢板简介: A572Gr50钢板是美国标准下的钢板牌号,属于是低合金高强度钢板的一种。目前钢板的强度要求比较高,但是对厚度还有要求,所以这些高强度钢板就应运而生。像是A572Gr50钢板就是在钢板内部添加少部分合金元素,使其通过特殊的热处理工艺之后,钢板的强度及韧性能得到部......
  • odoo8 pycharm debug 遇到的openerp.service.server: Evented Service (longpolling)
    odoo8pycharmdebug遇到的openerp.service.server:EventedService(longpolling)runningon0.0.0.0:8072@西安-张提供的指导 openerp/__init__.py 里面找到下面这几行,蓝色的是 新增的,红色的是把原来的代码注释掉 ......
  • 联发科MTK6853天玑720安卓核心板|5G AI 智能模块安卓主板开发板定制
    系统概述MT6853(联发科技天玑720)平台是工业级高性能、可运行android11.0操作系统的5GAI智能模块,支持NR-SA/NR-NSA/LTE-FDD(CAT-18)/LTE-TDD(CAT-18)/WCDMA/TDSCDMA/EVDO/CDMA/GSM等多种制式;支持WiFi5802.11a/b/g/n/ac,BTv2.1+EDR,3.0+HS,v4.1+HS,V5.1,支持Beidou......
  • The valid characters are defined in RFC 7230 and RFC 3986问题
    最近在ssm实践项目中遇到了ThevalidcharactersaredefinedinRFC7230andRFC3986这个问题,折腾了两天时间终于搞定了,记录一下心得。1、首先贴出报错日志:09-Apr-201914:55:11.427信息[http-nio-8089-exec-8]org.apache.coyote.http11.Http11Processor.serviceErrorpars......