从一道算法题说去2

今天的算法题是关于 字符串的最小编辑距离问题求解。

1. 什么是字符串编辑距离

编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，添加一个字符，删除一个字符。

例如将kitten一字转成sitting：

a. sitten （k→s） 

b. sittin （e→i） 

c. sitting （→g） 

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

2. 字符串的最小编辑距离即要求 给定两个字符串A和B，使得用最小的编辑距离达到 A=B

3. 求解两个字符串A和B的最小编辑距离，利用动态规划的思想。

a. 假设状态dp[i][j] 表示的是字符串A的子串 A[0-i]和字符串B的子串B[0-j]的最小编辑距离，那么有如下几个结论

i = 0，j = 0，dp[0][0] = 0，两个空串最小编辑距离为0

i = 0，j > 0，dp[i][j] = j，字符串A的子串为空则编辑距离为字符串B的子串长度 j

i > 0，j = 0，dp[i][j] = i，字符串B的子串为空则编辑距离为字符串A的子串长度 i

i > 0，j > 0，A[i] = B[j]，dp[i][j] = dp[i-1][j-1]，字符串A的子串最后一个字符等于字符串B子串的最后一个字符

i > 0，j > 0，A[I] != B[j]，dp[i][j] = min{dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1}，dp[i-1][j] + 1表示的是字符串A的子串添加一个字符，dp[i][j-1]表示的是字符串B的子串添加一个字符，dp[i-1][j-1] + 1表示字符串A的子串替换一个字符。

b. 大家会发现这个思路和求LCS的思路几乎是一样的。

4. 代码

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 50
#define INT_MAX 0x7ffffff

// get min edit dis
int GetEditDis(const string& strOne, const string& strTwo) {
	int dp[MAX][MAX];
	int strOneLength = strOne.length();
	int strTwoLength = strTwo.length();

	for (int i = 0; i <= strOneLength; ++i) {
		dp[i][0] = i; // strTwo subStr is empty
	}
	for (int j = 0; j <= strTwoLength; ++j) {
		dp[0][j] = j; // strOne subStr is empty
	}

	for (int i = 0; i < strOneLength; ++i) {
		for (int j = 0; j < strTwoLength; ++j) {
			int strOneAdd, strTwoAdd, rep;
			strOneAdd = dp[i][j+1] + 1; // strOne add char
			strTwoAdd = dp[i+1][j] + 1; // strTwo add char
			strOne[i] == strTwo[j] ? rep = 0 : rep = 1;
			dp[i+1][j+1] = min(min(strOneAdd, strTwoAdd), dp[i][j]+rep);
		}
	}
	return dp[strOneLength][strTwoLength];
}

int main(int argc, char **argv) {
	string strOne = "kitten";
	string strTwo = "sitting";

	cout << GetEditDis(strOne, strTwo) << endl; // cout 3

	return 0;
}