字符串最短距离CalculateStringDistance（递归 or 动态规划）-CSDN博客

本文链接：https://blog.csdn.net/arhaiyun/article/details/11863239

本文介绍了一种计算两个字符串相似度的方法，即字符串距离。通过定义三种基本操作：字符修改、插入和删除，文章提供了两种实现方式——递归算法与动态规划算法，并展示了具体的代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

/*
CalculateStringDistance

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1.修改一个字符（如把“a”替换为“b”）。
2.增加一个字符（如把“abdd”变为“aebdd”）。
3.删除一个字符（如把“travelling”变为“traveling”）。
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案，都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，给定任意两个字符串，你是否能写出一个算法来计算出它们的距离？
date:2013/09/21
@author arhaiyun
*/

#include "stdafx.h"
#include <iostream>
#include <cstring>
using namespace std;

int minValue(int a, int b, int c);

int CalculateStrDistance(char* pDst, char* pSrc)
{
	if(pSrc == NULL || *pSrc == '\0')
		return strlen(pDst);
	
	if(pDst == NULL || *pDst == '\0')
		return strlen(pSrc);
	
	if(*pDst == *pSrc)
		return CalculateStrDistance(pDst + 1, pSrc + 1);
	
	//[1].pSrc前添加字符*pDst
	int m1 = CalculateStrDistance(pDst + 1, pSrc);
	//[2].删除pSrc第一个字符
	int m2 = CalculateStrDistance(pDst, pSrc + 1);
	//[3].修改pSrc前的第一个字符为*pDst
	int m3 = CalculateStrDistance(pDst + 1, pSrc + 1);
	
	int min = minValue(m1, m2, m3);
	
	return min + 1;
}

//[2].Solution_2 Dynamic Plan
int DPCalculateStrDistance(char* pDst, char* pSrc)
{
	int lenDst = strlen(pDst);
	int lenSrc = strlen(pSrc);
	
	int** c = new int*[lenSrc + 1];
	for(int i = 0; i < lenSrc + 1; i++)
	{
		c[i] = new int[lenDst + 1];
	}

	for(int i = 0; i <= lenSrc; i++)
	{
		c[i][0] = i;
	}
	
	for(int j = 0; j <= lenDst; j++)
	{
		c[0][j] = j;
	}
	
	for(int i = 1; i <= lenSrc; i++)
	{
		for(int j = 1; j <= lenDst; j++)
		{
			if(pSrc[i - 1] == pDst[j - 1])
			{
				c[i][j] =  c[i - 1][j - 1];
			}
			else
			{
				c[i][j] = minValue(c[i][j-1], c[i-1][j], c[i - 1][j - 1]) + 1;
			}
		}
	}
	
	int ret = c[lenSrc][lenDst];
	
	for(int i = 0; i <= lenSrc; i++)
		delete[] c[i];
	delete[] c;	

	return ret;
}

int minValue(int a, int b, int c)
{
	int min = (a > b) ? b : a;
	min = (min > c) ? c : min;
	
	return min;
}

int main(int argc, char* argv[])
{
	char pSrc[10] = "abcefg";
	//pSrc[3] = '\0';
	char pDst[10] = "cabdefg";
	//pDst[3] = '\0';

	cout<<"String distance:"<<CalculateStrDistance(pDst, pSrc)<<endl;
	cout<<"DP String distance:"<<DPCalculateStrDistance(pDst, pSrc)<<endl;

	system("pause");
	return 0;
}