【删除公共字符】问题

题目描述

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”
输入描述：
每个测试输入包含2个字符串
输出描述：
输出删除后的字符串
示例1:
输入
They are students. aeiou
输出
Thy r stdnts.

解题思路

1. 暴力法：采用暴力查找方式，如判断第一个串的字符是否在第二个串中，若不在则将该字符存到一个新字符串中的方式，<mark>效率为O(N^2)</mark>，效率太低，很难让人满意。
2. 将第二个字符串的字符都映射到一个 hashtable 数组中，用来判断一个字符是否在这个字符串；
   判断一个字符在第二个字符串，不要使用删除，这样效率太低，因为每次删除都伴随数据挪动。这里可以考虑使用将不在字符添加到一个新字符串，最后返回新新字符串。

代码实现

1. 暴力查找法

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string str1, str2, str3;
	getline(cin, str1);
	getline(cin, str2);

	int i = 0;
	
	while (str1[i])
	{
		if (str2.find(str1[i], 0) == str2.npos)
		{
			str3 += str1[i];
		}
		++i;
	}

	cout << str3 << endl;

	return 0;
}

2.hashtable 法

#include<iostream>
#include<string>

using namespace std;

int main()
{
	// 注意这里不能使用cin接收，因为cin遇到空格就结束了。
	string str1, str2;
	//cin>>str1;
	//cin>>str2;
	getline(cin, str1);
	getline(cin, str2);
	// 使用哈希映射思想先str2统计字符出现的次数
	int hashtable[256] = { 0 };
	for (size_t i = 0; i < str2.size(); ++i)
	{
		hashtable[str2[i]]++;
	}
	// 遍历str1，str1[i]映射hashtable对应位置为0，则表示这个字符在
	// str2中没有出现过，则将他+=到ret。注意这里最好不要str1.erases(i)
	// 因为边遍历，边erase，容易出错。
	string ret;
	for (size_t i = 0; i < str1.size(); ++i)
	{
		if (hashtable[str1[i]] == 0)
			ret += str1[i];
	}
	cout << ret << endl;
	return 0;
}