首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

剔除字符串中的某些字母O(N)时间O(1)空间

2012-09-24 
删除字符串中的某些字母O(N)时间O(1)空间这个方法是用了hash方法,将要删除的字母先用数组下表表示,如果要

删除字符串中的某些字母O(N)时间O(1)空间

这个方法是用了hash方法,将要删除的字母先用数组下表表示,如果要删除,则标记为1.不需要删除的标记为0

这个方法在删除元素的时候比较巧妙,它对要删除的字符并不主动删除,而是将空间留在那里,让后面不需要被删除的字符去覆盖。

具体实现如下:

string& f(string& str,const string& deles){bitset<256> hash;hash.reset();for (int i=0;i<deles.size();i++){hash[deles[i]]=1;}int slow=0,fast=0;while(fast<str.size()){if (hash[str[fast]]==1){fast++;//跳过表示删除了,准备被后面留下来的字符覆盖continue;}str[slow++]=str[fast++];}str.resize(slow);return str;}int main( void ) {string s="They are students.";cout<<s<<endl;cout<<f(s,"aeiou")<<endl;return 0;}

剔除字符串中的某些字母O(N)时间O(1)空间

热点排行