P1532 字符串编辑距离 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年3月20日 21:38

字符串编辑距离题解：

P1532

回复 0 | 赞 0 | 浏览 635

DP基本问题要明白DP数组的含义，即前i/j个字符的字符串编辑距离递推公式的含义以及dp数组的初始化 #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; int minDistance(string word1,string word2){ int m = word1.size(); int n = word2.size(); ...

2023年2月13日 11:19

计算字符串编辑距离通解方法

P1532

回复 0 | 赞 0 | 浏览 3.6k

原理：给出一个初始化矩阵，逐位比较两个字符串，待修改的矩阵对应为行，被比较的矩阵对应位列若字符串对应的位相同，则让该矩阵位直接让这一位的矩阵的等于左上对角的值否则，有三种情况，分别是： ①：等于上面矩阵位加一 ②：等于左上角矩阵位加一 ③：等于左边矩阵位加一最后该矩阵位取上面三种情况中最小的一中。最右下角的一位保存的就是字符串编辑距离 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=1e9; const int ...

2022年7月11日 17:50

套公式题解（C++dp）

P1532

回复 0 | 赞 3 | 浏览 6.2k

#include<bits/stdc++.h> using namespace std; const int MAX = 1005; int dp[MAX][MAX]; string a,b; //dp[i][j]是指字符串1中的前i个字符和字符串2中的前j个字符的编辑距离 int main(){ cin>>a>>b; int lena = a.length(); int lenb = b.length(); memset(dp, 0, sizeof(dp)); //initia...

2022年3月20日 15:55

C++

P1532

回复 0 | 赞 0 | 浏览 4.8k

2020年5月28日 09:39

经典dp

P1532

回复 0 | 赞 0 | 浏览 9.6k

#define ll long long #define vec vector<int> #define inf 0x3f3f3f3f #define MAX 1005 #define P pair<ll,ll> #define MOD 1000000 int main() { string a, b; int dp[MAX][MAX]; while (cin >> a >> b) { a = ' ' + a, b = ' ' + b; int l1 = a.size(), l...

题目字符串编辑距离

题解数量5

热门题解

1 套公式题解（C++dp）

2 计算字符串编辑距离通解方法

3 经典dp

4 C++

5 字符串编辑距离题解：