考虑两个字符串string1和String2.
我的代码的主要目的是仅从string1中删除String2的元素。
下面是我的代码
string sring1,string2;
cin>>string1>>string2;
for(int i = 0; i<string2.length(); i++){
string1.erase(std::remove(string1.begin(), string1.end(),string2.at(i) ), string1.end());
}
cout<<string1;
上面代码的问题在于，它删除了string1中string2的所有元素，而我只想从string1中删除string2的特定元素，其余的都保持原样
这里是示例输出
输入:abbccdef
abc
必需输出:bcdef
我的输出:def
约束:1≤string2≤string1≤10^5
请帮助修改我的代码。
您可以执行:
#include <iostream>
#include <string>
int main() {
std::string s1 = "abbccdef";
std::string s2 = "abc";
for (std::string::size_type i = 0; i < s2.length(); ++i) {
for (std::string::size_type j = 0; j < s1.length(); ++j) {
if (s1[j] == s2[i]) {
s1.erase(j, 1);
break;
}
}
}
std::cout << s1 << std::endl;
}
输出:
# ./a.out
bcdef
OP对该问题进行了修正，目前正在寻找该问题的最优解。
解决方案:
假设string1的大小为N，string2的大小为M，则该解决方案的复杂度为O(n+m)，因为这两个字符串都只解析一次。
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string s1 = "abbccdef";
std::string s2 = "abc";
std::vector<int> count(128, 0);
for (std::string::size_type i = 0; i < s2.length(); ++i) {
++count[s2[i]];
}
std::string::size_type j = 0;
while (j < s1.length()) {
if (count[s1[j]] != 0) {
--count[s1[j]];
s1.erase(j, 1);
continue;
}
++j;
}
std::cout << s1 << std::endl;
return 0;
}
输出:
# ./a.out
bcdef
假设string1包含string2中的所有字符，则可以执行以下操作:
int pos = 0; // keep track of last deleted char position
for(auto c : string2)
string1.erase(pos = string1.find(c, pos), 1); // update new pos and erase char
这将在两个字符串上执行一次线性传递。 如果字符串2中有字符串1中没有的字符，则可以添加对std::string::npos的附加检查。
这是一个演示。
