首页 > 其他分享 >Leetcode【编辑距离】

Leetcode【编辑距离】

时间:2024-07-15 13:27:36浏览次数:18  
标签:删除 距离 编辑 word1 个字符 word2 操作 Leetcode dp

72. 编辑距离

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解题思路

  1. 定义状态:

    • 定义二维数组 dp,其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作次数。
  2. 初始化:

    • 如果 word1 或 word2 为空,则只需将另一个字符串的所有字符插入或删除。例如:
      • dp[i][0] = i,表示将 word1 的前 i 个字符转换为空字符串的操作次数,即 i 次删除操作。
      • dp[0][j] = j,表示将空字符串转换成 word2 的前 j 个字符的操作次数,即 j 次插入操作。
  3. 状态转移:

    • 通过遍历 word1 和 word2 中的每个字符,计算 dp[i][j] 的值。对于每对字符 (i, j)
      • 插入操作:将 word1 的前 i 个字符转换成 word2 的前 j 个字符的操作次数,可以通过在 word2 中插入第 j 个字符得到,即 dp[i][j-1] + 1
      • 删除操作:将 word1 的前 i 个字符转换成 word2 的前 j 个字符的操作次数,可以通过删除 word1 中的第 i 个字符得到,即 dp[i-1][j] + 1
      • 替换操作:将 word1 的前 i 个字符转换成 word2 的前 j 个字符的操作次数,如果 word1 的第 i 个字符与 word2 的第 j 个字符不同,则需要替换,即 dp[i-1][j-1] + 1;如果相同,则不需要额外的操作,即 dp[i-1][j-1]
  4. 选择最小操作次数:

    • 对于每个 (i, j),选择插入、删除和替换操作中的最小值来更新 dp[i][j]
      dp[i][j] = Math.min(w2dowm, Math.min(w2up, update));
      
      其中 w2dowm 是删除操作的结果,w2up 是插入操作的结果,update 是替换操作的结果。
  5. 结果:

    • 最终 dp[n][m] 即为将 word1 转换为 word2 所需的最小操作次数。
public int minDistance(String word1, String word2) {
    // 获取字符串word1的长度
    int n = word1.length();
    // 获取字符串word2的长度
    int m = word2.length();
    // 如果其中一个字符串长度为0,则返回另一个字符串的长度,即为插入或删除操作的次数
    if (n * m == 0) {
        return n + m;
    }
    // 创建一个二维数组dp,dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最小操作次数
    int[][] dp = new int[n + 1][m + 1];
    // 初始化dp数组
    dp[0][0] = 0;
    // 初始化第一列,即将word1的前i个字符变为空字符串所需的操作次数
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    // 初始化第一行,即将空字符串变成word2的前j个字符所需的操作次数
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }
    // 遍历字符串word1的每个字符
    for (int i = 1; i <= n; i++) {
        // 遍历字符串word2的每个字符
        for (int j = 1; j <= m; j++) {
            // w2up表示插入操作,将word1的前i-1个字符转换成word2的前j个字符,再插入一个字符
            int w2up = dp[i - 1][j] + 1;
            // w2dowm表示删除操作,将word1的前i个字符转换成word2的前j-1个字符,再删除word2的第j个字符
            int w2dowm = dp[i][j - 1] + 1;
            // update表示替换操作,将word1的前i-1个字符转换成word2的前j-1个字符,如果word1的第i个字符与word2的第j个字符不同,则需要替换
            int update = dp[i - 1][j - 1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                update += 1;
            }
            // 取三种操作中的最小值作为dp[i][j]的值
            dp[i][j] = Math.min(w2dowm, Math.min(w2up, update));
        }
    }
    // 返回将word1转换成word2所需的最小操作次数,即dp[n][m]
    return dp[n][m];
}

标签:删除,距离,编辑,word1,个字符,word2,操作,Leetcode,dp
From: https://blog.csdn.net/wudi6688/article/details/140429387

相关文章

  • LeetCode 1530. Number of Good Leaf Nodes Pairs
    原题链接在这里:https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/description/题目:Youaregiventhe root ofabinarytreeandaninteger distance.Apairoftwodifferent leaf nodesofabinarytreeissaidtobegoodifthelengthof thesh......
  • leetcode周赛 - 406
    100352.交换后字典序最小的字符串给你一个仅由数字组成的字符串 s,在最多交换一次 相邻 且具有相同 奇偶性 的数字后,返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数,则它们具有相同的奇偶性。例如,5和9、2和4奇偶性相同,而6和9奇偶性不......
  • 算法学习笔记(8.6)-编辑距离问题
    目录Question:动态规划思路:第一步:思考每轮的决策,定义状态,从而得到dp表第二步:找出最优子结构,进而推导出状态转移方程第三步:确定边界条件和状态转移顺序代码实现:图例:空间优化:代码如下编辑距离,也称为Levenshtein距离,指两个字符串之间互相转化的最少修改次数,通常用于在信......
  • LeetCode 144. 二叉树的前序遍历
    更多题解尽在https://sugar.matrixlab.dev/algorithm每日更新。组队打卡,更多解法等你一起来参与哦!LeetCode144.二叉树的前序遍历,难度中等。classSolution{publicvoidpreorderTraversal(TreeNoderoot,List<Integer>ans){if(root==null)re......
  • 24暑假算法刷题 | Day11 | LeetCode 150. 逆波兰表达式求值,239. 滑动窗口最大值,347.
    目录150.逆波兰表达式求值题目描述题解239.滑动窗口最大值题目描述题解347.前K个高频元素题目描述题解150.逆波兰表达式求值点此跳转题目链接题目描述给你一个字符串数组tokens,表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个......
  • 24暑假算法刷题 | Day9 | LeetCode 151. 反转字符串中的单词,28. 找出字符串中第一个匹
    目录151.反转字符串中的单词题目描述题解28.找出字符串中第一个匹配项的下标题目描述题解459.重复的子字符串题目描述题解卡码网55.右旋字符串题目描述题解151.反转字符串中的单词点此跳转题目链接题目描述给你一个字符串s,请你反转字符串中单词的顺......
  • 一起学习LeetCode热题100道(11/100)
    11.滑动窗口最大值(学习)给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例1:输入:nums=[1,3,-1,-3,5,3,6,7],k=3输出:[3,3,5,......
  • 福昕高级PDF编辑器专业版2024.2.0安装教程
    1、下载安装包2、双击安装程序进行安装3、修改安装位置,点击安装4、等待安装5安装完成,一定不能立即启用不要点击立即启用6、将patch的应用程序放到安装目录下面,双击启动7、点击应用8、执行完成,打开软件就可以用了如遇到福昕高级PDF编辑器失败,提示:本机已安装......
  • LeetCode 3091. 执行操作使数据元素之和大于等于 K(贪心、数学)
    3091.执行操作使数据元素之和大于等于K思路:数学思维题。先执行操作一让1加到k的平方根向上取整的数t,然后执行操作二,达到数组和>=k即可。classSolution{public:intminOperations(intk){intt=ceil(sqrt(k));return(k+t-1)/t+t-2;}......
  • Vim:最受欢迎的编辑器之一
    目录前言1.Vim的基本情况1.1Vim的起源与发展1.2Vim的工作模式2.Vim受欢迎的原因2.1强大的功能2.1.1丰富的快捷键2.1.2高度可定制化2.1.3强大的插件系统2.2使用方便性2.2.1跨平台支持2.2.2轻量级和高效2.2.3离线操作3.Vim与其他编辑器的比较3.1与现代ID......