博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
处女座与复读机
阅读量:6208 次
发布时间:2019-06-21

本文共 1049 字,大约阅读时间需要 3 分钟。

链接:

来源:牛客网

一天,处女座在牛客算法群里发了一句“我好强啊”,引起无数的复读,可是处女座发现复读之后变成了“处女座好强啊”。处女座经过调查发现群里的复读机都是失真的复读机,会固定的产生两个错误。一个错误可以是下面的形式之一:

1.       将任意一个小写字母替换成另外一个小写字母

2.       在任意位置添加一个小写字母

3.       删除任意一个字母

处女座现在在群里发了一句话,他收到了一个回应,他想知道这是不是一个复读机。

思路:

  dp[i][j]表示第i个字符变成j个字符的最小步数。

  错误形式有3种:dp[i][j]=min(dp[i-1][j], dp[i][j-1])+1;这是表示删除或者增加1个字符的情况。

         dp[i][j]=min(dp[i][j], dp[i-1][j-1]+(s[i-1]!=t[j-1]));便是错误一个字符

#include
#include
#include
using namespace std;const int maxn = 1005;char s[105], t[105];int dp[maxn][maxn];int n, m;int main(){ cin >> s >> t; n = strlen(s); m = strlen(t); for (int i = 0; i <= n; ++i)dp[i][0] = i; for (int i = 0; i <= m; ++i)dp[0][i] = i; for (int i = 1; i <= n;++i) for (int j = 1; j <= m; ++j) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])+1; dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (s[i - 1] != t[j - 1]?1:0)); } if (dp[n][m] <= 2)cout << "YES" << endl; else cout << "NO" << endl;}

 

转载于:https://www.cnblogs.com/ALINGMAOMAO/p/10339606.html

你可能感兴趣的文章
AlphaGo Zero用它来调参?【高斯过程】到底有何过人之处?
查看>>
Linux平台Oracle多个实例启动说明
查看>>
bash腳本編程之三 条件判断及算数运算
查看>>
php cookie
查看>>
linux下redis安装
查看>>
弃 Java 而使用 Kotlin 的你后悔了吗?| kotlin将会是最好的开发语言
查看>>
JavaScript 数据类型
查看>>
量子通信和大数据最有市场突破前景
查看>>
StringBuilder用法小结
查看>>
UVa 10252-Common Permutation
查看>>
CSS - 修改input - placeholder 和 readonly 的样式
查看>>
android studio :cannot resolve symbol R
查看>>
paper 20 :color moments
查看>>
代码大全
查看>>
博客园作业4--数组
查看>>
DataTable.ImportRow()与DataTable.Rows.Add()的区别
查看>>
程序集、应用程序配置及App.config和YourSoft.exe.config .
查看>>
二叉树的基本操作及应用(三)
查看>>
A SimpleDataStore
查看>>
朱晔和你聊Spring系列S1E3:Spring咖啡罐里的豆子
查看>>