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

72. 编辑距离(leetcode)

时间:2024-09-10 22:13:20浏览次数:7  
标签:字符 相同 int 编辑 word1 72 word2 leetcode

https://leetcode.cn/problems/edit-distance/

class Solution {
    public int minDistance(String word1, String word2) {
        // 经典题编辑距离
        // f[i][j]表示word1前i个字符中选择进行操作,word2前j个字符进行选择进行操作相同的最少步数
        // 以word1[i],word2[j]是否相同划分子集
        // 相同则不需要考虑word1[i],word2[j],考虑对之前的字符进行操作
        // 不同则考虑三个操作,增,删,改,增是加一个字符使得相同,删是删一个字符相同,改是改一个字符使得相同
        // 这里有个难点:增和删对于word1和word2都是等价的,目的都是使两个字符串相等,增word1等价删word2,增word2等价删word1
        // 因此可以看做只有删word1,删word2,改word1,删word1,则考虑前i-1个元素,删word2则考虑前j-1个元素
        // 改一定会相等,因此考虑i-1,j-1个元素
        // 有min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
        // f[i][j] = if(word1[i]==word2[j]) f[i-1][j-1]
        //           else f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
        // 根据定义有f[1~n][0]=1~n,f[0][1~n]=1~n
        int[][] f=new int[510][510];
        for(int i=1;i<=word1.length();i++)f[i][0]=i;
        for(int i=1;i<=word2.length();i++)f[0][i]=i;
        for(int i=1;i<=word1.length();i++)
            for(int j=1;j<=word2.length();j++)
            {
                if(word1.charAt(i-1)==word2.charAt(j-1))f[i][j]=f[i-1][j-1];
                else f[i][j]=Math.min(f[i-1][j],Math.min(f[i][j-1],f[i-1][j-1]))+1;
            }
        return f[word1.length()][word2.length()];
    }
}

 

标签:字符,相同,int,编辑,word1,72,word2,leetcode
From: https://www.cnblogs.com/lxl-233/p/18407340

相关文章

  • 使用dnSpyEx对.NET Core程序集进行反编译、编辑和调试
    前言说到.NET相关的反编译工具大家脑海里第一个想到的工具是什么?ILSpy、dnSpy、还是dotPeek?咱们今天的主要内容是讲讲dnSpyEx(dnSpyEx是dnSpy项目的非官方Fork维护版本)这个开源的.NET程序集反编译、编辑和调试工具该如何使用。4款免费且实用的.NET反编译工具.NET反编译神器ILSpy怎么......
  • 583. 两个字符串的删除操作(leetcode)
    https://leetcode.cn/problems/delete-operation-for-two-strings/solutions/两种做法,1.直接dp2.转换题意,思考成LCSclassSolution{publicintminDistance(Stringword1,Stringword2){//编辑距离的简化版//f[i][j]表示word1前i个字符中选择,wo......
  • LeetCode Hot100刷题记录-234.回文链表
    题目:给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。PS:回文序列是向前和向后读都相同的序列。解题思路:遍历链表,将每个元素存放入一个新的数组中。遍历完成后,再用两个指针前后遍历数组来判断两个数字是否相等。/***Def......
  • 线性dp:LeetCode122.买卖股票的最佳时机ll
    买卖股票本文所讲解的内容与LeetCode122.买卖股票的最佳时机ll,这道题题意相同,阅读完本文后可以自行挑战一下力扣链接题目叙述:给定一个长度为N的数组,数组中的第i个数字表示一个给定股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交......
  • CF1672F2 Checker for Array Shuffling 题解
    题目链接点击打开链接题目解法我怎么F1都不会做/llF1:由原始值向最终值连边如果是排列的话,操作次数显然为\(n-\)环数拓展到非排列的情况,即相同数之间的下标可以选择顺序,要求分出来的环数最大直接考虑上面的这东西,让我进入了死胡同。。先给出一个结论:最大环数的最小值是......
  • 51nod 1720 祖玛
    51nod1720祖玛这又是一个区间dp,但这题又和其他的不一样,这题又用记忆化搜索,但是多学一种方法也没事,但其实用搜索后就模拟即可了。#include<bits/stdc++.h>usingnamespacestd;//定义全局变量intn;//数组长度intdp[505][505];//dp[l][r]表示在区间[l,r]之间的......
  • leetcode day06 动态规划之解码方法I和II
    91.解码方法该题类似于爬楼梯方法一:动态规划对于给定的字符串s,设它的长度为n,其中的字符从左到右依次为s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串s的解码方法数。具体地,设f i 表示字符串s的前i个字符s[1..i]的解码方法数。在进行状态转移......
  • LeetCode之数组/字符串
    88.合并两个有序数组classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){//这个循环将nums2中的元素逐个复制到nums1中从索引m开始的位置for(inti=0;i<n;i++){nums1[i+m]=nums2[i];......
  • LeetCode: 2552. 统计上升四元组 动态规划 时间复杂度O(n*n)
    2552.统计上升四元组today2552.统计上升四元组题目描述给你一个长度为n下标从0开始的整数数组nums,它包含1到n的所有数字,请你返回上升四元组的数目。如果一个四元组(i,j,k,l)满足以下条件,我们称它是上升的:0<=i<j<k<l<n且nums[i]<nums[k]<num......
  • 115. 不同的子序列(leetcode)
    https://leetcode.cn/problems/distinct-subsequences/submissions/563375885/这题比较有难度,具体不太好想到,需要以是否选择s[i]来划分子集这位描述的很清楚,不做过多赘述classSolution{publicintnumDistinct(Strings,Stringt){//f[i][j]表示s中前i个......