力扣72-编辑距离

article/2024/6/13 21:55:25

题目链接

记忆化搜索:
解题关键:每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示
临界条件:当 i 或 j 小于0时,表示该字符串为空,编辑距离确定为 y+1 或 x+1

int dp[501][501]={0};
class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(),n=word2.size();for(int i=0;i<m;i++)for(int j=0;j<n;j++)dp[i][j]=INT_MAX;return dfs(m-1,n-1,word1,word2);}int dfs(int x,int y,string word1,string word2){if(x<0)return y+1;if(y<0)return x+1;if(dp[x][y]!=INT_MAX)return dp[x][y];if(word1[x]==word2[y])return dfs(x-1,y-1,word1,word2);int ans= min(min(dfs(x-1,y,word1,word2),dfs(x,y-1,word1,word2)),dfs(x-1,y-1,word1,word2))+1;dp[x][y]=ans;return ans;}
};

动态规划(区间dp)
由状态转移方程直接推得,自底向上
转移方程dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1 此处 i / j 表示剩余待匹配长度

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();//dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1vector<vector<int>>dp(n+1, vector<int>(m+1, INT_MAX));//dp[i][0] = i  and dp[0][j] = jfor(int i=0;i<=n;i++){dp[i][0] = i;}for(int j=0;j<=m;j++){dp[0][j] = j;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(word1[i-1]==word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] =min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;}}}return dp[n][m];}
};

http://www.ngui.cc/article/show-2100789.html

相关文章

第6章 动态响应页面内容

1 什么是动态页面 之前案例虽然收到了表单提交的参数但是收到了404错误,因为确实没有页面与请求URI对应,解决这个办法就可以使用动态页面技术,就是动态生成页面内容。 动态响应页面(Dynamic Response Page)是一种动态生成的Web页面,其内容可以根据用户的请求和其他动态变…

linux ndk编译搭建测试

一、ndk下载 NDK 下载 | Android NDK | Android Developers 二、ndk环境变量配置 ndk解压&#xff1a; unzip android-ndk-r26d-linux.zip 环境变量配置&#xff1a; export NDK_HOME/rd/own/test/android-ndk-r26d/ export PATH$PATH:$NDK_HOME 三、编译测试验证 …

word标题格式批量设置方法

1.直接全选ctrlA 全选后然后统一进行编辑&#xff08;适用于标题是紧挨着的情况&#xff09; 2.直接修改对应几级标题格式&#xff0c;然后应用于自己所需要的标题&#xff08;可能会导致上面修改后但是下面不会自动更改&#xff0c;此时用第三种方法&#xff09; 点击[开始…

互联网洗护工厂系统能带来哪方面的便捷

我们的干洗店洗衣洗鞋小程序&#xff0c;为您带来便捷、智能的洗衣洗鞋体验。只需轻触屏幕&#xff0c;即可在线预约洗衣服务&#xff0c;随时随地&#xff0c;无需等待&#xff0c;告别繁琐的电话预约。 用户成为会员&#xff0c;您将独享专属优惠与折扣&#xff0c;更有积分累…

如何配置Always On 可用性组

配置SQL Server的Always On可用性组是一个相对复杂的过程,涉及多个步骤。以下是一个简化的配置流程: 先决条件: 确保你正在使用SQL Server的企业版或开发人员版,因为Always On可用性组功能在这两个版本中是可用的。部署Always On可用性组需要一个Windows Server故障转移群集…

Python内置函数oct()详解

Python中的oct()函数是一个内置函数&#xff0c;用于将一个整数转换成它的八进制字符串表示。 函数定义 oct()函数的基本语法如下&#xff1a; oct(x)x&#xff1a;一个整数。 函数返回x的八进制表示&#xff0c;以字符串形式。 基本用法 将整数转换为八进制 number 64…

vue3 使用WebAssembly 实战

在Vue 3中使用WebAssembly&#xff08;WASM&#xff09;的一个基本示例包括以下几个步骤&#xff1a; 1. 准备WebAssembly模块 首先&#xff0c;你需要一个WebAssembly模块。假设你已经有了一个编译好的.wasm文件&#xff0c;比如名为example.wasm。 2. 加载WebAssembly模块…

几个人脸库对于面部动作识别的功能比较

经粗略研究,insightface只能识别面部特征点的位置,根据这些位置不能直接推出一个人是否在睡觉。 OpenFace 是一个高级的面部行为分析工具,它能够识别和分析多种面部动作单位(Facial Action Coding System, FACS),这些动作单位是根据面部肌肉活动定义的。每个动作单位(A…

golang实现普通升管理员权限

golang实现普通升管理员权限 package mainimport ("fmt""os""path/filepath""runtime""syscall""unsafe""golang.org/x/sys/windows""golang.org/x/sys/windows/registry" )var (modntdll …

Delphi 7打造RESTful API客户端

分享一下如何使用Delphi 7来实现一个简单的RESTful API客户端。或许你会问&#xff0c;为啥选择Delphi 7&#xff1f;这不是一个已经有些年头的开发工具了吗&#xff1f;没错&#xff0c;Delphi 7确实是个“老古董”了&#xff0c;但有时&#xff0c;出于一些旧的项目或特定的需…