基础算法题 —— 计算字符串的编辑距离（动态规划）

题解

在题目所求的编辑距离是指字符串 a 转换成字符串 b 所需最小的 *** 作步骤。
a[i] != b[j] 时，要使 a[i] == b[j] 可使用的 *** 作步骤如下：
①、a[i] 可替换成 b[j]。
②、字符串 a 下标为 i 的位置插入字符 b[j]，a[i+1] = 原a[i]…。
③、字符串 b 下标为 j 的位置插入字符 a[i]，b[j+1] = 原b[j]…。

由于字符串可以通过“插入”字符的 *** 作进行改变，要得到相同的两个字符串就要从串头到串尾进行匹配。利用这一特点我们可以利用动态规划的思路来解决。

①、创建 dp 二维数组，在 a、b 字符串头插入两个特殊字符，便于进行 dp 数组初始化。
②、当 a[i] == b[j] 时，不用 *** 作，dp[i][j] = dp[i-1][j-1]
③、当 a[i] != b[j] 时， 需要 *** 作，dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1

代码

#include
#include
using namespace std;

int main() {
	string s1, s2;
	int k;
	cin>>s1>>s2;
	s1.insert(0, 1, ' ');    //在字符串s1下标0位置插入1个' '字符
	s2.insert(0, 1, ' ');
	int len1 = s1.length();
	int len2 = s2.length();
	
    int dp[len1+1][len2+1];
	for(int i=0; i<len1; i++) dp[i][0]=i;   //空字符串需要转换为s1最少经过步骤次数
	for(int i=0; i<len2; i++) dp[0][i]=i;   
	for(int i=1; i<len1; i++) {
		for(int j=1; j<len2; j++) {
            s1[i]==s2[j] ? k = 0 : k = 1;   
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
			dp[i][j] = min(dp[i][j], dp[i-1][j-1]+k);
		}
	}
	cout<<dp[len1-1][len2-1];
	
	return 0;
}