欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短编辑距离(动态规划超详细填表法)

程序员文章站 2022-07-14 19:34:01
...

链接:https://www.nowcoder.com/questionTerminal/9649617be3bf42288f50758df4310655
来源:牛客网
 

UNIX系统下有一个行编辑器ed,它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”,经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”,这三步操作后,内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作,我们称它们的编辑距离为3。

现在给你两个任意字符串(不包含空格),请帮忙计算它们的最短编辑距离。

思路分析:

此题是一道动态规划类的题目,这类题目不是特别的难,下面分享一下我的做题思路。

拿到一道动态规划类的题目要做的有三件事:

1、阅读理解题目,并且简化问题。

2、设定初始值,填表。

3、在表格的数据当中寻找规律。

由于动态规划类的题目,它的下一个结果仅仅取决于上一次填表的结果,这样一层一层迭代下来最终就能得到想要的结果。填表的过程要严格遵循题目指定的规则。

我们来看这道题的表格:

最短编辑距离(动态规划超详细填表法)

 

一般初值的设定不是一成不变的,需要根据题目来自己尝试,并不是一次就能成功的所以有时候需要一点灵感。可以看到我用颜色标记出来的是设定的初值。填完表之后,在表中找规律,发现要是正好在对角线上的两个字符相等那么就取它左上角的数字。要是不相同就去它上面、左面、左上的元素中最小值再加1,在表的右下角就是最终的结果。

在填表的时候要填什么数字完全是按照规则来的,填完之才能够找规律。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/* 它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作 */
int deal_shortest(string str1, string str2)
{
	int len1 = str1.size();
	int len2 = str2.size();
	int i = 0;
	int j = 0;
	vector<vector<int>> m_v(len1+1,vector<int>(len2+1,0));//生成二维数组用于填表
	/* 设定初始值 ,vector一旦设定存储空间那么它就成了C语言中的数组,存在边界*/
	m_v[0][0] = 0;
	for (i=1;i<=len1;++i)
	{
		m_v[i][0] = i;
	}
	for (i=1;i<=len2;++i)
	{
		m_v[0][i] = i;
	}
	for (i=1;i<=len1;++i)
	{
		for (j=1;j<=len2;++j)
		{
			if (str1[i-1]==str2[j-1])
			{
				m_v[i][j] = m_v[i - 1][j - 1];
			}
			else
			{
				m_v[i][j] = min(m_v[i][j - 1], min(m_v[i - 1][j - 1], m_v[i - 1][j]))+1;
			}
		}
	}
	return m_v[len1][len2];
}
int main()
{
	string str1;
	string str2;
	while (cin>>str1>>str2)
	{
		cout<<deal_shortest(str1, str2)<<endl;
		str1.clear();
		str2.clear();
	}
	system("pause"); 
	return 0;
}

 

 

 

 

 

 

 

 

 

相关标签: 最短编辑距离