编辑距离模板题

深碍√TFBOYSˉ_ 2022-09-06 00:28 168阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

// Problem: P2758 编辑距离
    // Contest: Luogu
    // URL: https://www.luogu.com.cn/problem/P2758
    // Memory Limit: 125 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    using namespace std;
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    
    
    const int N=2e3+100;
    int dp [N][N];
    
    
    int calc(string a, string b)
    { 
    	int n = a.length(), m = b.length();
    	if(n * m == 0) return n + m;
    	
    	// 空变到对用的字符，都需要对应的i个操作
    	rep(i, 0, n) dp[i][0] = i; 
    	rep(i, 0, m) dp[0][i] = i;
    	
    	rep(i, 1, n)
    		rep(j, 1, m)
    		{ 
    			int x = dp[i-1][j] + 1; // 变
    			int y = dp[i][j-1] + 1; // 加
    			int z = dp[i-1][j-1]; // 左下角
    			if(a[i-1] != b[j-1]) // 最后一个不同
    				z += 1;
    			dp[i][j] = min(x, min(y, z));
    		}
    	return dp[n][m];
    }
    
    void solve()
    { 
    	string a, b;
    	cin >> a >> b;
    	cout << calc(a, b);
    }
    
    int main()
    { 
    	solve();
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20220829/fd17890ada464817807b01dc3101c775.png

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关 72. 编辑距离——【Leetcode每日一题】

72. 编辑距离给你两个单词 `word1` 和 `word2`，请返回将 `word1` 转换成 `word2` 所使用的最少操作数。你可以对一个单词进行如下

柔情只为你懂/ 2024年03月26日 00:08/ 0 赞/ 109 阅读

相关 72. 编辑距离

72. 编辑距离题干分析解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式 3.

Love The Way You Lie/ 2023年10月16日 17:59/ 0 赞/ 35 阅读

相关理解编辑距离

顾名思义，编辑距离（Edit distance）是一种距离，用于衡量两个字符串之间的远近程度，方式是一个字符串至少需要多少次基础变换才能变成另一个字符串，可应用在拼写检查、判断

朴灿烈づ我的快乐病毒、/ 2022年12月17日 13:56/ 0 赞/ 225 阅读

相关 72. 编辑距离

> 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。 > > 你可以对一个单词进行如下三种操作： > > 插入

拼搏现实的明天。/ 2022年10月10日 01:51/ 0 赞/ 191 阅读

相关编辑距离模板题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

深碍√TFBOYSˉ_/ 2022年09月06日 00:28/ 0 赞/ 169 阅读

相关编辑距离Edit distance

http://[blog.csdn.net/pipisorry/article/details/46383947][blog.csdn.net_pipisorry_articl

谁借莪１个温暖的怀抱￠/ 2022年08月05日 04:29/ 0 赞/ 375 阅读

相关编辑距离

编辑距离算法算法过程 1. str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.leng

比眉伴天荒/ 2022年06月11日 04:24/ 0 赞/ 254 阅读

相关编辑距离

一、问题描述设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）

逃离我推掉我的手/ 2022年06月10日 09:08/ 0 赞/ 286 阅读

相关 leetcode 72. 编辑距离

![1588437-20190516145616651-338815526.png][] / 定义状态： DP[i][j]其中i表示word1前i个字

悠悠/ 2021年12月21日 01:27/ 0 赞/ 395 阅读

相关【动态规划】编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一

缺乏、安全感/ 2021年10月03日 02:38/ 0 赞/ 459 阅读