当前位置: 首页 > news >正文

淄博营销网站建设武汉建站公司

淄博营销网站建设,武汉建站公司,wordpress首页调用分类版块,公司让我做网站负责人Leetcode 72.编辑距离 题目描述 给定两个单词 word1 和 word2,返回将 word1 转换为 word2 所使用的最少操作数。 你可以对一个单词执行以下三种操作之一: 插入一个字符删除一个字符替换一个字符 示例 1: 输入: word1 "horse", word2 &…

Leetcode 72.编辑距离

题目描述

给定两个单词 word1word2,返回将 word1 转换为 word2 所使用的最少操作数。

你可以对一个单词执行以下三种操作之一:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 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 -> exention (替换 'i' 为 'e')
exention -> exection (替换 'n' 为 'c')
exection -> execuion (替换 'e' 为 'u')
execuion -> execution (替换 'i' 为 't')

Java 实现代码

public class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的最小编辑距离int[][] dp = new int[m + 1][n + 1];// 初始化 DP 数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;  // 如果 word1 为空,需要插入 j 个字符} else if (j == 0) {dp[i][j] = i;  // 如果 word2 为空,需要删除 i 个字符} else {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], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;// 三种操作的最小值:删除、插入、替换}}}}return dp[m][n];}
}

解题思路

编辑距离问题是一个经典的动态规划问题,我们可以通过动态规划来逐步解决。

  1. 状态定义

    • 定义 dp[i][j]word1[0..i-1]word2[0..j-1] 之间的最小编辑距离。
  2. 状态转移

    • 如果 word1[i-1] == word2[j-1],则 dp[i][j] = dp[i-1][j-1],表示如果两个字符相等,编辑距离不变。
    • 如果 word1[i-1] != word2[j-1],则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1,表示三种操作的最小值:
      • dp[i-1][j] + 1:删除一个字符。
      • dp[i][j-1] + 1:插入一个字符。
      • dp[i-1][j-1] + 1:替换一个字符。
  3. 初始状态

    • dp[i][0] = i,表示 word1[0..i-1] 和空字符串的编辑距离是 i(即删除所有字符)。
    • dp[0][j] = j,表示 空字符串 和 word2[0..j-1] 的编辑距离是 j(即插入所有字符)。
  4. 目标

    • 最终结果为 dp[m][n],其中 mn 分别是 word1word2 的长度。

复杂度分析

  • 时间复杂度O(m * n),其中 mn 分别是 word1word2 的长度。我们需要计算一个 m x n 的 DP 表格,每个元素的计算是常数时间。

  • 空间复杂度O(m * n),我们需要一个 m x n 的 DP 表格来存储子问题的解。

执行过程示例

假设 word1 = "horse"word2 = "ros",我们通过动态规划计算编辑距离。

  1. 初始化 DP 数组:

    dp = [[0, 1, 2, 3],[1, 0, 0, 0],[2, 0, 0, 0],[3, 0, 0, 0],[4, 0, 0, 0],[5, 0, 0, 0]
    ]
    
  2. 填充 DP 数组:

    • i = 1, j = 1word1[0] = 'h', word2[0] = 'r',不相等,dp[1][1] = min(dp[0][1], dp[1][0], dp[0][0]) + 1 = 1
    • i = 1, j = 2word1[0] = 'h', word2[1] = 'o',不相等,dp[1][2] = min(dp[0][2], dp[1][1], dp[0][1]) + 1 = 2
    • i = 1, j = 3word1[0] = 'h', word2[2] = 's',不相等,dp[1][3] = min(dp[0][3], dp[1][2], dp[0][2]) + 1 = 3
    • i = 2, j = 1word1[1] = 'o', word2[0] = 'r',不相等,dp[2][1] = min(dp[1][1], dp[2][0], dp[1][0]) + 1 = 2
    • i = 2, j = 2word1[1] = 'o', word2[1] = 'o',相等,dp[2][2] = dp[1][1] = 1
    • i = 2, j = 3word1[1] = 'o', word2[2] = 's',不相等,dp[2][3] = min(dp[1][3], dp[2][2], dp[1][2]) + 1 = 2
    • i = 3, j = 1word1[2] = 'r', word2[0] = 'r',相等,dp[3][1] = dp[2][0] = 2
    • i = 3, j = 2word1[2] = 'r', word2[1] = 'o',不相等,dp[3][2] = min(dp[2][2], dp[3][1], dp[2][1]) + 1 = 2
    • i = 3, j = 3word1[2] = 'r', word2[2] = 's',不相等,dp[3][3] = min(dp[2][3], dp[3][2], dp[2][2]) + 1 = 3
    • i = 4, j = 1word1[3] = 's', word2[0] = 'r',不相等,dp[4][1] = min(dp[3][1], dp[4][0], dp[3][0]) + 1 = 3
    • i = 4, j = 2word1[3] = 's', word2[1] = 'o',不相等,dp[4][2] = min(dp[3][2], dp[4][1], dp[3][1]) + 1 = 3
    • `i = 4, j = 3

word1[3] = ‘s’, word2[2] = ‘s’,相等,dp[4][3] = dp[3][2] = 2`。

  • i = 5, j = 1word1[4] = 'e', word2[0] = 'r',不相等,dp[5][1] = min(dp[4][1], dp[5][0], dp[4][0]) + 1 = 4
  • i = 5, j = 2word1[4] = 'e', word2[1] = 'o',不相等,dp[5][2] = min(dp[4][2], dp[5][1], dp[4][1]) + 1 = 4
  • i = 5, j = 3word1[4] = 'e', word2[2] = 's',不相等,dp[5][3] = min(dp[4][3], dp[5][2], dp[4][2]) + 1 = 3
  1. 最终 DP 数组:

    dp = [[0, 1, 2, 3],[1, 1, 2, 3],[2, 2, 1, 2],[3, 2, 2, 3],[4, 3, 3, 2],[5, 4, 4, 3]
    ]
    
  2. 结果为 dp[5][3] = 3,即编辑距离为 3。

http://www.ritt.cn/news/19509.html

相关文章:

  • wordpress配置七牛云cdnseo比较好的优化方法
  • 网站的空间是网站搜索优化排名
  • 手机上怎么做网站创业简易网站制作
  • 自己用iis怎么建设网站干净无广告的搜索引擎
  • 中国室内设计网站排名足球世界排名国家最新
  • 做球球棒棒糖网站源码威海网站制作
  • 网站换域名怎么办百度电脑端网页版入口
  • 品牌vi设计包括哪些搜索引擎优化 简历
  • 去国外做非法网站吗东莞日增感染人数超25万
  • 潍坊市网站建设seo怎么收费seo
  • wordpress农业为什么seo工资不高
  • 网站漂浮图片代码seo排名大概多少钱
  • 陕西省住房城乡建设部门户网站加强服务保障满足群众急需i
  • 襄樊做网站小白如何学电商运营
  • 网站开发实习报告太极seo
  • 单位网站设计制作seo实战密码电子版
  • 景区网站建设方案 费用唐山seo排名外包
  • 做ppt好的模板下载网站百度官网推广平台
  • wordpress导航站源码收录优美图片官网
  • 中企动力网站建设百度seo排名优化联系方式
  • 做网站失败seo站长博客
  • 在线收录广州网站优化工具
  • 一个公司怎么做网站都放些什么seo网站推广培训
  • 爆推联盟官网企业网站seo多少钱
  • 做色情网站会怎么样百度推广关键词质量度
  • 深圳公司注册办理流程一键优化是什么意思
  • 上海外贸网站优化百度站内搜索
  • 做电商网站用什么软件seo关键词优化推广价格
  • 一个微信可以做两个网站支付semester是什么意思
  • 深圳seo优化服务商成都排名seo公司