【删除公共字符】问题

题目描述

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

解题思路

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

代码实现

暴力查找法 #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; }