首页 > 代码库 > 编辑距离
编辑距离
编辑距离概念描述：
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
- sitten （k→s）
- sittin （e→i）
- sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
问题：找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符
解析：
首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式：
- if i == 0 或 j == 0，edit(i, j) = i + j
- if i > 0 且j == 0，edit(i, j) = i
- if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
#include <iostream>#include <string>#include <vector>#include <stdio.h>using std::cout;using std::endl;using std::vector;using std::string;int min(int a, int b){ return a < b ? a : b;}int edit(string src, string dst){ vector<vector<int>> distances; for (int i = 0; i <= src.size(); i++) { distances.push_back(vector<int>(dst.size() + 1)); } for (int i = 0; i < distances.size(); i++) { distances[i][0] = i; } for (int i = 0; i < distances[0].size(); i++) { distances[0][i] = i; } for (int i = 1; i < distances.size();i++) { for (int j = 1; j < distances[i].size(); j++) { int sub = 0; if (src[i - 1] == dst[j - 1]) { sub = 0; } else { sub = 1; } distances[i][j] = min(min(distances[i][j - 1] + 1, distances[i - 1][j] + 1), distances[i - 1][j - 1] + sub); } } printf(" "); for (int i = 0; i < dst.size(); i++) { printf("%2c", dst[i]); } printf("\n"); for (int i = 0; i < distances.size(); i++) { printf("%2c", i != 0 ? (src[i - 1]) : ‘ ‘); for (int j = 0; j < distances[i].size(); j++) { printf("%2d", distances[i][j]); } printf("\n"); } cout << endl; return distances[distances.size() - 1][distances[0].size() - 1];}int main(void){ string str1 = "kitten"; string str2 = "sitting"; int r = edit(str1, str2); cout << "the distance is : " << r << endl; getchar(); return 0;}
运行结果:
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。