输入两个字符串，从第一字符串中删除第二个字符串中所有的字符（转自CSDN）...

末蓝、 2021-10-18 12:36 235阅读 0赞

转自：[http://blog.csdn.net/alexingcool/article/details/6786590][http_blog.csdn.net_alexingcool_article_details_6786590]

例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。

思路：不可避免的是遍历第一个字符串，如果遍历一个字符，都需要去第二个字符串中查找其存不存在，那么复杂度会是O(nm)，当然由于字符数有限，所以m是个常量。关于查找速度最快的当然是hash表，对于8位字符，size=2^8足矣。

关于删除字符，后面的字符要往前移，如果每删除一个就移一次，O(n^2)这复杂度实在太高，仅仅用快慢指针就可以搞定，这个方法非常有用，比如求解循环链表。

初始化：快慢指针指向第一个字符

循环：如果快指针指的是不需要的字符，将值赋给慢指针后，快慢指针同时++;如果快指针指向待删除字符，那么直接++；

终止：快指针指向'\\0'

**\[cpp\]**   [view plain][http_blog.csdn.net_alexingcool_article_details_6786590] [copy][http_blog.csdn.net_alexingcool_article_details_6786590]

1.  /\*     
2.  \* Copyright (c) 2011 alexingcool. All Rights Reserved.     
3.  \*/  
4.  \#include <iostream>  
5.    
6.  \#define NUMBER 256  
7.    
8.  **using** **namespace** std;  
9.    
10. **char** firstArray\[\] = "They are students.";  
11. **char** secondArray\[\] = "aeiou";  
12. **const** **int** firstSize = **sizeof** firstArray / **sizeof** \*firstArray;  
13. **const** **int** secondSize = **sizeof** secondArray / **sizeof** \*secondArray;  
14.   
15. **bool** flag\[NUMBER\];  
16.   
17. **void** deleteArray(**char** \*firstArray, **char** \*secondArray)  
18. \{  
19.     **if**(firstArray == NULL || secondArray == NULL)  
20.         **return**;  
21.   
22.     **for**(**int** i = 0; i < NUMBER; i++) \{  
23.         flag\[i\] = **false**;  
24.     \}  
25.   
26.     **for**(**int** i = 0; i < secondSize; i++) \{  
27.         **int** pos = **static\_cast**<**int**>(secondArray\[i\]);  
28.         flag\[pos\] = **true**;  
29.     \}  
30.   
31.     **char** \*fast = firstArray, \*slow = firstArray;  
32.   
33.     **while**(\*fast != '\\0') \{  
34.         **if**(flag\[\*fast\] == **false**) \{  
35.             \*slow = \*fast;  
36.             slow++;  
37.         \}  
38.         fast++;  
39.     \}  
40.     \*slow = 0;  
41. \}  
42.   
43. **void** main()  
44. \{  
45.     deleteArray(firstArray, secondArray);  
46.     cout << firstArray << endl;  
47. \}

结果如下：

![0_13163101470f22.gif][]

转载于:https://www.cnblogs.com/wb118115/archive/2012/06/06/2538359.html

[http_blog.csdn.net_alexingcool_article_details_6786590]: http://blog.csdn.net/alexingcool/article/details/6786590
[0_13163101470f22.gif]: /images/20211018/935835895f0745cfa46dff84739c1bdb.png