95、动态规划-编辑距离

2024-05-09 23:52
文章标签 动态 规划 距离 编辑 95

本文主要是介绍95、动态规划-编辑距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归暴力解法

递归方法的基本思想是考虑最后一个字符的操作,然后根据这些操作递归处理子问题。

递归函数定义:定义一个递归函数 minDistance(i, j),表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。

递归终止条件

  • 如果 i == 0,意味着 word1 为空,此时将 word1 转换成 word2 的前 j 个字符就需要 j 次插入操作。
  • 如果 j == 0,意味着 word2 为空,此时将 word1 的前 i 个字符转换成空字符串需要 i 次删除操作。

递归转移方程

  • 如果 word1[i-1] == word2[j-1],则当前两个字符相等,不需要操作,所以 minDistance(i, j) = minDistance(i-1, j-1)
  • 如果不相等,则可以进行插入、删除或替换操作,转移方程为:
    • 插入:minDistance(i, j) = minDistance(i, j-1) + 1
    • 删除:minDistance(i, j) = minDistance(i-1, j) + 1
    • 替换:minDistance(i, j) = minDistance(i-1, j-1) + 1
  • 取三者的最小值。

代码如下:

public class Solution {// 主方法,用于外部调用,传入两个字符串public int minDistance(String word1, String word2) {// 调用递归助手函数,初始化i和j为字符串的长度,从字符串尾部开始比较return minDistanceHelper(word1, word2, word1.length(), word2.length());}// 递归助手函数,用于计算两个字符串的最小编辑距离private int minDistanceHelper(String word1, String word2, int m, int n) {// 如果第一个字符串为空,则转换的代价是第二个字符串的长度(即插入n次)if (m == 0) return n;// 如果第二个字符串为空,则转换的代价是第一个字符串的长度(即删除m次)if (n == 0) return m;// 如果两个字符串的当前字符相等,则不需要操作,递归考虑前一个字符if (word1.charAt(m - 1) == word2.charAt(n - 1)) {return minDistanceHelper(word1, word2, m - 1, n - 1);}// 计算插入操作的代价:将word2的第n个字符插入到word1的末尾,然后继续处理剩余的字符串int insert = minDistanceHelper(word1, word2, m, n - 1) + 1;// 计算删除操作的代价:删除word1的第m个字符,然后继续处理剩余的字符串int delete = minDistanceHelper(word1, word2, m - 1, n) + 1;// 计算替换操作的代价:将word1的第m个字符替换为word2的第n个字符,然后继续处理剩余的字符串int replace = minDistanceHelper(word1, word2, m - 1, n - 1) + 1;// 返回三种操作中的最小值,即为到当前位置为止的最小编辑距离return Math.min(Math.min(insert, delete), replace);}
}

但是重复计算效率很慢,改成动态规划:

动态规划方法

动态规划方法的核心思想是使用一个二维数组 dp 来存储中间结果,其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。通过填充这个数组,我们可以逐步构建出从一个空字符串到完整 word2,再从完整 word1word2 的转换路径。

初始化:
  • dp[0][j]:将空字符串转换为 word2 的前 j 个字符,需要 j 次插入操作。
  • dp[i][0]:将 word1 的前 i 个字符转换为空字符串,需要 i 次删除操作。
状态转移方程:
  • 如果 word1[i-1] == word2[j-1],则 dp[i][j] = dp[i-1][j-1],因为最后一个字符已经匹配,不需要额外操作。
  • 如果 word1[i-1] != word2[j-1],则可以从以下三个可能的操作中选择最小成本的:
    • 插入:dp[i][j] = dp[i][j-1] + 1
    • 删除:dp[i][j] = dp[i-1][j] + 1
    • 替换:dp[i][j] = dp[i-1][j-1] + 1

代码如下:

public class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化dp数组for (int i = 0; i <= m; i++) {dp[i][0] = i;  // 从word1的i字符变为空字符串}for (int j = 0; j <= n; j++) {dp[0][j] = j;  // 从空字符串变为word2的j字符}// 填充dp数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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] + 1), dp[i-1][j-1] + 1);}}}return dp[m][n];}
}

这篇关于95、动态规划-编辑距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/974845

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Java计算经纬度距离的示例代码

《Java计算经纬度距离的示例代码》在Java中计算两个经纬度之间的距离,可以使用多种方法(代码示例均返回米为单位),文中整理了常用的5种方法,感兴趣的小伙伴可以了解一下... 目录1. Haversine公式(中等精度,推荐通用场景)2. 球面余弦定理(简单但精度较低)3. Vincenty公式(高精度,

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

Python+Tkinter实现Windows Hosts文件编辑管理工具

《Python+Tkinter实现WindowsHosts文件编辑管理工具》在日常开发和网络调试或科学上网场景中,Hosts文件修改是每个开发者都绕不开的必修课,本文将完整解析一个基于Python... 目录一、前言:为什么我们需要专业的Hosts管理工具二、工具核心功能全景图2.1 基础功能模块2.2 进