在一个字符串中删除在另一个字符串中出现的字符
程序员文章站
2023-12-21 16:16:46
...
题目:两个字符串A、B,从A中剔除存在于B中的字符。比如A=“hello world”,B=”er”,那么剔除之后A变为”hllowold”。空间复杂度要求是O(1),时间复杂度越优越好。
思路:hash+双指针。
对需要剔除的字符串做hash处理,查询复杂度为O(1), 字符总数为128, 所以空间复杂度为O(1).
双指针用于对对初始串的替换,在O(n)时间内完成替换,方法是设置两个指针: fast 和 slow。当碰到不是需要剔除的字符时,将fast指针指向的内容赋给slow,fast和slow都向前走一步;当碰到的是需要剔除的字符是,就fast指针向前走一步。这样就把那个需要删除的字符给隔过去了
#include<iostream>
#include<string>
using namespace std;
void hash1(const string &str, int arr[])
{
if (str.empty())
{
return;
}
for (int i = 0; i < str.length(); i++)
{
arr[str[i]] = 1;
}
}
void delectstr(string &str,const int arr[])
{
if (str.empty())
{
return;
}
char *first = &str[0];//创建两个指向数组头部的指针
char *last = &str[0];//last作用是存储不被删除的,而first起到一个探路的作用,找到不被删除的字符将其地址给first
while (*first!='\0')//直到循环完毕
{
if (arr[*first]==0)//如果这个不是要删除的字符
{
*last = *first;//换地址
last++;//last向后继续
}
first++;//first向后继续
}
*last = '\0';//已经遍历完毕,所以将结束 字符放在*last的位置上,这样所有不被删除的字符就放在了前面
}
int main()
{
int hasharr[128];
memset(hasharr,0,sizeof(hasharr));
string str1 = "a bc defgp";
string str2 = "jjjjdcvg b";
cout << str1 << endl;
hash1(str2,hasharr);
delectstr(str1,hasharr);
cout << str1.data() << endl;
//或者如*****意因为删除后变短了,所以不能用length 输出
//for (int i = 0; str1[i]!='\0'; i++)
//{
// cout << str1[i];
//}
return 0;
}