从 string1 中删除 string2 的必需元素

Question

考虑 2 个字符串 string1 和 string2。
我的代码的主要 objective 是仅从字符串 1 中删除字符串 2 的元素。
这是我的代码

 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
美国广播公司
要求的输出：bcdef
我的输出：def

CONSTRAINTS:1≤|string2|≤|string1|≤10^5
请帮助修改我的代码。

Answer 1

你可以这样做：

#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已经修改了问题，现在正在寻找这个问题的最佳解决方案。

解决方案：

记录string2的字符在数组中出现的次数
解析 string1，如果在数组中找到字符，则减少它的计数并将其从 string1 中删除。

假设字符串 1 的大小为 n，字符串 2 的大小为 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

Answer 2

假设 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

这会对两个字符串进行一次线性传递。如果 string2 中的字符不在 string1 中，您可以为 std::string::npos 添加额外的检查。

这是 demo。

从 string1 中删除 string2 的必需元素

Remove the required elements of string2 from string1

c++

string

std

编辑