首页 > 其他分享 >72. 编辑距离(leetcode)

72. 编辑距离(leetcode)

时间:2024-04-23 17:34:55浏览次数:26  
标签:String int 编辑 word1 72 word2 n2 leetcode

https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked

这是一个难题,关于序列DP的,官方的题解较为难懂,这里有一位前辈解释的很好

这里的状态定义是: dp[i][j]表示word1的前i个字母,转换成 word2的前j个字母的最小步数
class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; 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]), dp[i - 1][j]) + 1;
            }
        }
        return dp[n1][n2];  
    }
}

 

标签:String,int,编辑,word1,72,word2,n2,leetcode
From: https://www.cnblogs.com/lxl-233/p/18153355

相关文章

  • mipi dsi4线720P国产gowin lattice crosslink配套屏Fpga dsi
     1.产品概述    显示屏LCDMIPIDSI4lane,支持分辨率720*1280,60HZ彩色显示。用于对接国产GOWIN的NR-9C的开发板和LATTICE的CROSSLINK开发板,显示MIPIDSI 功能。      MIPIDSI是4-LANE,MIPI速率在480MHZ。支持LP模式初始化和HS模式显示数据发送。    ......
  • 低开开发笔记(四):实现编辑器内拖拽
    好家伙,本篇我们来说说,编辑器内如何实现拖拽完整代码已开源https://github.com/Fattiger4399/ph-questionnaire.git  0.效果预览 1.思路1.1.视图操作分析这一块是这一章节最核心的部分到 用户进行了什么操作?(1)点击编辑器中第一个组件(2)松开(3)在setter中修改第一......
  • DOM的编辑
    1.创建DocumentBuilderFactory对象,通过DocumentBuilder解析目标文件到Document对象中。DocumentBuilderFactoryfa=DocumentBuilderFactory.newInstance();DocumentBuilderdb=fa.newDocumentBuilder();Filef=newFile();//括号内填入目标文件的相对路径。Documentdo......
  • LeetCode 1331. Rank Transform of an Array
    原题链接在这里:https://leetcode.com/problems/rank-transform-of-an-array/description/题目:Givenanarrayofintegers arr,replaceeachelementwithitsrank.Therankrepresentshowlargetheelementis.Therankhasthefollowingrules:Rankisanintegers......
  • [leetcode 周赛] 100276. 最短路径中的边
    solution使用dijkstra算法求出顶点0到每个顶点的最小距离dp[i]然后再从n-1开始遍历,如果dp[to]+w==dp[from],这条边符合条件importjava.util.*;classSolution{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();......
  • LeetCode 2326. Spiral Matrix IV
    原题链接在这里:https://leetcode.com/problems/spiral-matrix-iv/description/题目:Youaregiventwointegers m and n,whichrepresentthedimensionsofamatrix.Youarealsogiventhe head ofalinkedlistofintegers.Generatean mxn matrixthatconta......
  • LeetCode 1424. Diagonal Traverse II
    原题链接在这里:https://leetcode.com/problems/diagonal-traverse-ii/description/题目:Givena2Dintegerarray nums,return allelementsof nums indiagonalorderasshowninthebelowimages.Example1:Input:nums=[[1,2,3],[4,5,6],[7,8,9]]Output:[1,4,......
  • 本地部署Llama3-8B/72b 并进行逻辑推理测试
    美国当地时间4月18日,Meta开源了Llama3大模型,目前开源版本为8B和70B。Llama3模型相比Llama2具有重大飞跃,并在8B和70B参数尺度上建立了LLM模型的新技术。由于预训练和后训练的改进,Llama3模型是目前在8B和70B参数尺度上存在的最好的模型。训练后程序的改进大大降低了错误拒绝率,改善......
  • LeetCode三则
    63.不同路径II一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网格中的障碍物和空......
  • leetcode回文数
    给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,为121-。因此......