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

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# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

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.