DP20. 计算字符串的编辑距离
描述
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
输入描述
每组用例一共2行，为输入的两个字符串
输出描述
每组用例输出一行，代表字符串的距离
示例1
输入:
abcdefg abcdef
输出:
1
C++ 解法, 执行用时: 1ms, 内存消耗: 632KB, 提交时间: 2017-08-17
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//空间可以优化成O(n)
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
for (int i = 1; i <= s2.length(); i++) dp[0][i] = i;
for (int i = 1; i <= s1.length(); i++) dp[i][0] = i;
for(int i=1;i<=s1.length();i++)
for (int j = 1; j <= s2.length(); j++) {
int min1 = min(dp[i - 1][j], dp[i][j - 1]) + 1;
dp[i][j] = min((s1[i - 1] == s2[j - 1] ? 0 : 1) + dp[i - 1][j - 1], min1);
}
cout << dp[s1.size()][s2.size()] << endl;
}
}
C 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2021-08-01
#include <stdio.h>
#include <string.h>
int main(void){
const int sz = 500;
char rows[sz], cols[sz];
while(gets(rows) != NULL && gets(cols) != NULL)
{
int line[strlen(rows) + 1];
for(int i = 0; i <= strlen(rows); ++i)
line[i] = i;
for(int i = 1; i <= strlen(cols); ++i)
{
int prev = line[0];
line[0] = i;
for(int j = 1; j <= strlen(rows); ++j)
{
int t = line[j];
if(rows[j-1] == cols[i-1])
line[j] = prev;
else
{
if(line[j] > prev)
{
line[j] = prev;
}
if(line[j] > line[j-1])
{
line[j] = line[j-1];
}
++line[j];
}
prev = t;
}
}
printf("%d\n", line[strlen(rows)]);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2021-09-15
#include <stdio.h>
int main()
{
char rows[1000], cols[1000];
while(gets(rows)&&gets(cols))
{
int line[strlen(rows) + 1];
for(int i = 0; i <= strlen(rows); ++i)
line[i] = i;
for(int i = 1; i <= strlen(cols); ++i)
{
int prev = line[0];
line[0] = i;
for(int j = 1; j <= strlen(rows); ++j)
{
int t = line[j];
if(rows[j-1] == cols[i-1])
line[j] = prev;
else
{
if(line[j] > prev)
line[j] = prev;
if(line[j] > line[j-1])
line[j] = line[j-1];
++line[j];
}
prev = t;
}
}
printf("%d\n", line[strlen(rows)]);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 324KB, 提交时间: 2021-11-25
#include <stdio.h>
#include <string.h>
int min(int a ,int b)
{
return ((a)>(b)?(b):(a));
}
int get_diff2(char* s1, char* s2)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
int *dp = (int*)malloc(sizeof(int*)*(len2+1));
//int *dp2 = (int*)malloc(sizeof(int*)*(len2+1));
int i,j;
int tmp1,tmp2,tmp3;
int dp1,dp2; //优化空间用
if(*s1=='\0')
return strlen(s2);
if(*s2=='\0')
return strlen(s1);
for (j=0; j<=len2; j++)
dp[j] = j;
for (i=1; i<=len1; i++)
{
dp1=i;
for(j=1; j<=len2; j++)
{
tmp1 = dp[j] +1;
tmp2 = dp1+1;
tmp3 = (s1[i-1]!=s2[j-1]?dp[j-1]+1:dp[j-1]);
dp2 = min(min(tmp1,tmp2),tmp3);
if(j==1)
dp[0]=i;
if(j>=2)
dp[j-1] = dp1;
dp1 = dp2;
}
dp[j-1] = dp1;
}
free(dp);
return dp1;
}
int main(){
char A[500];
char B[500];
while(gets(A)&&gets(B))
{
printf("%d\n",get_diff2(A,B));
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2022-03-20
//当两个字符串都为空串，那么编辑距离为0；
//当其中一个字符串为空串时，那么编辑距离为另一个非空字符串的长度；
//当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种情况最小值即可：
//1、长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；
//2、长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；
//3、长度分别为 i-1 和 j-1 的字符串的编辑距离已知，此时考虑两种情况，若第i个字符和第j个字符不同，那么加1即可；如果不同，那么不需要加1。
#include <stdio.h>
int main()
{
char rows[1000], cols[1000];
while(gets(rows)&&gets(cols))
{
int line[strlen(rows) + 1];
for(int i = 0; i <= strlen(rows); ++i)
line[i] = i;
for(int i = 1; i <= strlen(cols); ++i)
{
int prev = line[0];
line[0] = i;
for(int j = 1; j <= strlen(rows); ++j)
{
int t = line[j];
if(rows[j-1] == cols[i-1])
line[j] = prev;
else
{
if(line[j] > prev)
line[j] = prev;
if(line[j] > line[j-1])
line[j] = line[j-1];
++line[j];
}
prev = t;
}
}
printf("%d\n", line[strlen(rows)]);
}
return 0;
}