题目描述

给定两个字符串 S1 和 S2，S=S1−S2 定义为将 S1 中包含的所有在 S2 中出现过的字符删除后得到的字符串。

你的任务就是计算 S1−S2。

输入格式
共两行，第一行包含字符串 S1，第二行包含字符串 S2。

输出格式
输出共一行，表示 S1−S2 的结果。

数据范围
两个给定字符串的长度都不超过 104。

样例

输入样例：
They are students.
aeiou
输出样例：
Thy r stdnts.

算法1

(暴力枚举) $O(n^2)$

C++ 代码

#include <iostream>

using namespace std;

string s1, s2;

bool check_exist(char c)
{
    for(auto a : s2)
        if(a == c)
            return true;
    return false;        

}

int main()
{

    string res;
    getline(cin, s1); //输入带空格的字符串
    getline(cin, s2);

    int n = s1.size(), m = s2.size();
    for(int i = 0; i < n; i ++)
    {
        if(!check_exist(s1[i]))
        {
            res = res + s1[i];
        }

    }
    cout << res;
    puts("");

    return 0;
}

算法2

利用哈希表查找 $O(n)$

unordered_set
unordered_set.count(c)  统计c在哈希表出现的次数

时间复杂度 $O(n)$

C++ 代码

#include <iostream>
#include <unordered_set>
using namespace std;

string s1, s2;

int main()
{

    string res;
    getline(cin, s1); //输入带空格的字符串
    getline(cin, s2);

    unordered_set<char> hash;

    for(auto c : s2) hash.insert(c);

    int n = s1.size(), m = s2.size();
    for(auto a : s1)
    {
        if(!hash.count(a))
            res = res + a;

    }
    cout << res;
    puts("");

    return 0;
}