c++ - 如何通过删除最少字符数来获取子字符串?
问题描述
在这个问题中,我们将 2 个字符串作为输入,例如 s1 和 s2。
现在,首先我们需要检查 s2 是否是 s1 的子序列。如果没有,打印没有。
但如果是,我们需要打印从 s1 中删除的最小字符数才能得到 s2。
例如-thistext 文本
在这里,不删除任何字符就可以直接找到文本,所以答案是 0。
例如-可爱的友谊脆
在这种情况下,答案是 9。
到目前为止我所做的,
#include <bits/stdc++.h>
using namespace std;
int checkIfSub(string s1, string s2, int m, int n)
{
int j = 0;
for(int i = 0; i < m && j < n; i++)
if(s1[i] == s2[j])
j++;
if(j == n)
return 0;
else
return 1;
}
int check(string s1, string s2)
{
int count = 0; string s3;
if(checkIfSub(s1, s2, s1.length(), s2.length()) == 1 || s2.length() > s1.length())
{
cout << "NO\n"; return 0;
}
int j = 0;
for(int i = 0; i < s1.length(); i++)
{
if(s1[i] == s2[j])
{
s3[j] = s1[j];
j++; continue;
}
count++;
}
cout << "YES " << count << "\n";
return 0;
}
int main() {
string s1, s2;
cin >> s1 >> s2;
check(s1, s2);
return 0;
}
我的代码适用于第二个示例,但在第一个示例中失败。
(这是我在网上阅读的一些采访中提出的问题。)
解决方案
尝试这样的事情:
#include <iostream>
#include <string>
using namespace std;
bool check(const string &s1, const string &s2, int &minToDelete)
{
minToDelete = 0;
bool anySubSeqFound = false;
if (s2.empty())
return false;
string::size_type first = 0;
while ((first = s1.find(s2[0], first)) != string::npos)
{
int numDeleted = 0;
bool isSubSeq = true;
string::size_type next = first + 1;
for(string::size_type j = 1; j < s2.size(); ++j)
{
string::size_type found = s1.find(s2[j], next);
if (found == string::npos)
{
isSubSeq = false;
break;
}
numDeleted += (found - next);
next = found + 1;
}
if (isSubSeq)
{
if (anySubSeqFound)
{
if (numDeleted < minToDelete)
minToDelete = numDeleted;
}
else
{
anySubSeqFound = true;
minToDelete = numDeleted;
}
}
++first;
}
return anySubSeqFound;
}
int main()
{
int minToDelete;
if (check("thistext", "text", minToDelete))
cout << "yes, delete " << minToDelete << endl;
else
cout << "no" << endl;
if (check("cutefriendship", "crisp", minToDelete))
cout << "yes, delete " << minToDelete << endl;
else
cout << "no" << endl;
}
推荐阅读
- liquibase - Liquibase 日志级别问题和许可证错误
- c# - ASP.NET Core MVC - 使用 Microsoft Authenticator 的多因素推送身份验证
- android - 由于反应本机邮件,Gradle 构建失败
- amazon-web-services - Cloudformation 应用程序负载均衡器弹性 IP 错误
- xml - 运行 testng.xml 以触发 testng 时会发生什么?
- apache-spark - Spark s3数据框选择失败:ConnectionClosedException内容长度过早结束
- vb.net - 我想将我的 AutoCAD 图层过滤器导出到另一个图形
- django - 在 Django 模板上显示上传的 csv 文件
- parsing - 无法使用格式 [strict_date_optional_time||epoch_millis] 解析 Logstash 中的日期
- node.js - 如何使用查询器在 mongoDB 中搜索单个字段?