在字符串中删除特定的字符--总结

　　这里提供除原文之外的另一种思路，不过好像不如原文中的好，先记下吧。
　　大致思路：把要删除的字符集（假设为char *del）看成一个模子，把它套在原字符串（假设为char *src）中进行比较，一开始，del的第一个字符和src的第一个字符比较，不相同就同时后移指针，如相同，就删除src中的字符，并且把后面的所有字符前移，继续比较这一位，这样一直比较，直到del的字符都比较完后，再进行第二轮。第二轮比较时，把del的首字符对准src的第二个字符，开始上述过程。这样直到src的最后一个字符对准del的第一个字符为最后一轮。
　　这样做的缺点就是每次删除一个字符之后，都要进行大量的字符移动，很耗时，这个也是原文中的方法重点解决的一个问题。
　　原文中用一个256长度的数组来做hash表，有点浪费了，因为hash表的值只可能为0或1，所以可以用int的每一位对应一个hash表中的元素，这样就只需要8个int就可以组成这个hash表，大大节省了空间。
　　另外，原文中有一个需要考虑的地方，最后在pSlow指针处赋值\0后，pSlow指针之后的空间（直到\0）应该free掉吧。
　　下面全部为原文引用：
　　题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入"They are students."和"aeiou"，则删除之后的第一个字符串变成"Thy r stdnts."。
　　分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，因为写程序操作字符串能很好的反映我们的编程基本功。
　　要编程完成这道题要求的功能可能并不难。毕竟，这道题的基本思路就是在第一个字符串中拿到一个字符，在第二个字符串中查找一下，看它是不是在第二个字符串中。如果在的话，就从第一个字符串中删除。但如何能够把效率优化到让人满意的程度，却也不是一件容易的事情。也就是说，如何在第一个字符串中删除一个字符，以及如何在第二字符串中查找一个字符，都是需要一些小技巧的。
　　首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符，需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话，对于一个长度为n的字符串而言，删除一个字符的时间复杂度为O(n)。而对于本题而言，有可能要删除的字符的个数是n，因此该方法就删除而言的时间复杂度为O(n2)。
　　事实上，我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想，当一个字符需要被删除的时候，我们把它所占的位置让它后面的字符来填补，也就相当于这个字符被删除了。在具体实现中，我们可以定义两个指针(pFast和pSlow)，初始的时候都指向第一字符的起始位置。当pFast指向的字符是需要删除的字符，则pFast直接跳过，指向下一个字符。如果pFast指向的字符是不需要删除的字符，那么把pFast指向的字符赋值给pSlow指向的字符，并且pFast和pStart同时向后移动指向下一个字符。这样，前面被pFast跳过的字符相当于被删除了。用这种方法，整个删除在O(n)时间内就可以完成。
　　接下来我们考虑如何在一个字符串中查找一个字符。当然，最简单的办法就是从头到尾扫描整个字符串。显然，这种方法需要一个循环，对于一个长度为n的字符串，时间复杂度是O(n)。
　　由于字符的总数是有限的。对于八位的char型字符而言，总共只有28=256个字符。我们可以新建一个大小为256的数组，把所有元素都初始化为0。然后对于字符串中每一个字符，把它的ASCII码映射成索引，把数组中该索引对应的元素设为１。这个时候，要查找一个字符就变得很快了：根据这个字符的ASCII码，在数组中对应的下标找到该元素，如果为0，表示字符串中没有该字符，否则字符串中包含该字符。此时，查找一个字符的时间复杂度是O(1)。其实，这个数组就是一个hash表。这种思路的详细说明，详见 本面试题系列的第13题
　　。
　　基于上述分析，我们可以写出如下代码：
　　////////////////////////////////////////////////// /////////////////////
　　// Delete all characters in pStrDelete from pStrSource
　　////////////////////////////////////////////////// /////////////////////
　　voidDeleteChars(char* pStrSource, constchar* pStrDelete)
　　{
　　if(NULL == pStrSource || NULL == pStrDelete)
　　return;
　　// Initialize an array, the index in this array is ASCII value.
　　// All entries in the array, whose index is ASCII value of a 
　　// character in the pStrDelete, will be set as 1.
　　// Otherwise, they will be set as 0.
　　constunsignedintnTableSize = 256;
　　inthashTable[nTableSize];
　　memset(hashTable, 0, sizeof(hashTable));
　　constchar* pTemp = pStrDelete;
　　while ('\0' != *pTemp)
　　{
　　hashTable[*pTemp] = 1;
　　++ pTemp;
　　}
　　char* pSlow = pStrSource;
　　char* pFast = pStrSource;
　　while ('\0' != *pFast)
　　{
　　// if the character is in pStrDelete, move both pStart and 
　　// pEnd forward, and copy pEnd to pStart. 
　　// Otherwise, move only pEnd forward, and the character
　　// pointed by pEnd is deleted
　　if(1 != hashTable[*pFast])
　　{
　　*pSlow = *pFast;
　　++ pSlow;
　　}
　　++pFast;
　　}
　　*pSlow = '\0';
　　}
　　原文地址：http://zhedahht.blog.163.com/blog/static/254111742 00801931426484/