题解 | #计算字符串的编辑距离#

// HJ52-3 计算字符串的编辑距离.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int dp[1001][1001];

int main()
{
	string s1, s2;
	while (cin >> s1 >> s2)
	{
		s1 = ' ' + s1;
		s2 = ' ' + s2;
		int l1 = s1.size(), l2 = s2.size();
		for (int i = 0; i < l1; i++)
		{
			dp[i][0] = i;
		}
		for (int j = 0; j < l2; j++)
		{
			dp[0][j] = j;
		}
		for (int i = 1; i < l1; i++)
		{
			for (int j = 1; j < l2; j++)
			{
				dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
				if (s1[i] != s2[j])
				{
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]+1);
				}
				else
				{
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
				}
			}
		}
		cout << dp[l1 - 1][l2 - 1];
	}
	return 0;
}