计算两个字符串的距离(递归搜索会爆栈)

2024-06-22 22:32

本文主要是介绍计算两个字符串的距离(递归搜索会爆栈),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

/*
很经典的可使用动态规划方法解决的题目,和计算两字符串的最长公共子序列相似。
设Ai为字符串A(a1a2a3 … am)的前i个字符(即为a1,a2,a3 … ai)
设Bj为字符串B(b1b2b3 … bn)的前j个字符(即为b1,b2,b3 … bj)
设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
当ai==bj时 显然 L(i,j) = L(i-1,j-1)
当ai!=bj时 若将它们修改为相等,则对两个字符串至少还要操作L(i-1,j-1)次若删除ai或在bj后添加ai,则对两个字符串至少还要操作L(i-1,j)次若删除bj或在ai后添加bj,则对两个字符串至少还要操作L(i,j-1)次此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1 
显然,L(i,0)=i,L(0,j)=j, 再利用上述的递推公式,可以直接计算出L(i,j)值。
*/
#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int main()
{string a,b;while(cin>>a>>b){memset(dp,0,sizeof(dp));for(int i=0; i<=a.size(); i++)dp[i][0]=i;for(int i=0; i<=b.size(); i++)dp[0][i]=i;for(int i=1; i<=a.size(); i++)for(int j=1; j<=b.size(); j++){if(a[i-1]==b[j-1]){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;}}cout<<dp[a.size()][b.size()]<<endl;}return 0;
}
/*
这道题是前几个月Google笔试的最后一道题,当时写的不好,有些细节没写出来,现在整理写一下。
题目描述:
对于不同的字符串,希望能够有办法判断其相似程度。定义了如下方法来把两个不同的字符串变得相同,具体的操作方法为:
1. 修改一个字符 (如把"a"替换为"b")
2. 增加一个字符 (如把"abc"变换为"aabc")
3. 删除一个字符 (如把"abc"变换为"bc")
比如,对于”abc”和”bc”两个字符串来说,可以通过增加/删除一个”a”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于”距离+1”的倒数。也就是说,”abc”和”bc”的距离为1,相似度为1/(1+1)=0.5。
给定任意两个字符串,写出一个算法来计算它们的相似度。
分析:
如果有两个字符串A和B,如果它们的第一个字符是相同的,只要计算A[2,…,lenA]和B[2,…,lenB]的距离。如果它们的第一个字符是不相同的,那么可以进行如下的操作。
1. 删除A的第一个字符,然后计算A[2,…,lenA]和B[1,…,lenB]的距离;
2. 删除B的第一个字符,然后计算A[1,…,lenA]和B[2,…,lenB]的距离;
3. 修改A的第一个字符为B的第一个字符,然后计算A[2,…,lenA]和B[2,…,lenB]的距离;
4. 修改B的第一个字符为A的第一个字符,然后计算A[2,…,lenA]和B[2,…,lenB]的距离;
5. 增加A的第一个字符到B第一个字符之前,然后计算A[2,…,lenA]和B[1,…,lenB]的距离;
6. 增加B的第一个字符到A第一个字符之前,然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
从上面的分析可以看出,如果A和B的第一个字符不相同,那么可以不管之后会变成什么样,就可以把上面的6个操作合并成下面3个。
1. 一步操作之后,计算A[2,…,lenA]和B[1,…,lenB]的距离;
2. 一步操作之后,计算A[1,…,lenA]和B[2,…,lenB]的距离;
3. 一步操作之后,计算A[2,…,lenA]和B[2,…,lenB]的距离。 
这个题目和计算两个字符串的相似度是一样的。点击打开链接
*/
#include<bits/stdc++.h>
using namespace std;
int dist(int pa,int pb,string a,string b)
{if(pa>=a.size()){if(pb>=b.size())return 0;else return b.size()-pb;}if(pb>=b.size()){if(pa>=a.size())return 0;else return a.size()-pa;}if(a[pa]==b[pb]){return dist(pa+1,pb+1,a,b);}else{int n1=dist(pa+1,pb,a,b);int n2=dist(pa,pb+1,a,b);int n3=dist(pa+1,pb+1,a,b);return min(n1,(n2,n3))+1;}return 0;
}
int main()
{string a,b;while(cin>>a>>b){cout<<dist(0,0,a,b)<<endl;}return 0;
}

这篇关于计算两个字符串的距离(递归搜索会爆栈)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085595

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python并行处理实战之如何使用ProcessPoolExecutor加速计算

《Python并行处理实战之如何使用ProcessPoolExecutor加速计算》Python提供了多种并行处理的方式,其中concurrent.futures模块的ProcessPoolExecu... 目录简介完整代码示例代码解释1. 导入必要的模块2. 定义处理函数3. 主函数4. 生成数字列表5.

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST