面试中经常会考到算法，下面分别讲如何删除一个字符串里的特定字符或特定字符串
一、
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
例如， 输入”i want to be a excellent programmers”和”aem”，则删除之后的第一个字符串变成”i wnt to b xcllnt progrrs"
分析：要编程完成这道题要求的功能可能并不难。毕竟，这道题的基本思路就是在第一 个字符串中拿到一个字符，在第二个字符串中查找一下，看它是不是在第二个字符串中。如果在的话，就从第一个字符串中删除。但如何能够把效率优化到让人 满意的程度，却也不是一件容易的事情。也就是说，如何在第一个字符串中删除 一个字符，以及如何在第二字符串中查找一个字符，都是需要一些小技巧的。
首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续 分配的。我们从字符串当中删除一个字符，需要把后面所有的字符往前移动一个 字节的位置。但如果每次删除都需要移动字符串后面的字符的话，对于一个长度 为 n 的字符串而言，删除一个字符的时间复杂度为 O(n)。而对于本题而言，有可 能要删除的字符的个数是 n，因此该方法就删除而言的时间复杂度为 O(n2)。
事实上，我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我 们可以设想，当一个字符需要被删除的时候，我们把它所占的位置让它后面的字 符来填补，也就相当于这个字符被删除了。在具体实现中，我们可以定义两个指 针(psou和 pkey)，初始的时候都指向第一字符的起始位置。当 psou 指向的字符是需要删除的字符，则 psou 直接跳过，指向下一个字符。如果 psou 指向的字符是不需要删除的字符，那么把 psou 指向的字符赋值给 pkey 指向的字符， 并且 psou 和 pkey同时向后移动指向下一个字符。这样，前面被psou 跳过的字符相当于被删除了。用这种方法，整个删除在 O(n)时间内就可以完成。
接下来我们考虑如何在一个字符串中查找一个字符。当然，最简单的办法就是从 头到尾扫描整个字符串。显然，这种方法需要一个循环，对于一个长度为 n 的字 符串，时间复杂度是 O(n)。 由于字符的总数是有限的。对于八位的 char 型字符而言，总共只有 28=256 个字 符。我们可以新建一个大小为 256 的数组，把所有元素都初始化为 0。然后对于 字符串中每一个字符，把它的 ASCII 码映射成索引，把数组中该索引对应的元素 设为１。这个时候，要查找一个字符就变得很快了：根据这个字符的 ASCII 码， 在数组中对应的下标找到该元素，如果为 0，表示字符串中没有该字符，否则字符串中包含该字符。此时，查找一个字符的时间复杂度是 O(1)。其实，这个数组 就是一个 hash 表。
基于上述分析，我们可以写出如下代码：
1 #define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 char * deleteStr(char *source, char *key)
6 {
7
8 int hashTable[256];
9 memset(hashTable, 0, sizeof(hashTable));
10 char *point_sou, *point_key;
11 point_sou = key;
12 while (*point_sou != ' ')//待删除字符在哈希表里赋值为1
13 {
14 hashTable[*point_sou] = 1;
15 point_sou++;
16 }
17 point_sou = source;
18 point_key = source;
19 while (*point_sou != ' ')
20 {
21 if (!hashTable[*point_sou])//哈希表不为1时不是待删除字符,将sou指针指向的字符赋给key指针指向的字符，将两指针同时向后移
22 {
23 *point_key = *point_sou;
24 point_key++;
25 }
26 point_sou++; //是待删除字符，sou指针继续向前移，key指针停留在待删除字符前
27 //下一次循环判断是不是待删除字符，不是，将sou指针指向的字符赋给key指针指向的字符，souce也就相当于删除了前面的字符
28
29 }
30 *point_key = ' ';
31 return source;
32
33 }
34
35 int main()
36 {
37 char p[] = "i want to be a excellent programmers";
38 char key[] = "aem";
39 printf("%s
", deleteStr(p, key));
40 }
二、
问题描述： 在给定字符串中查找所有特定子串并删除，如果没有找到相应子串，则不作任何操作。
要求实现函数：int delete_sub_str(const char *str, const char *sub_str, char *result_str)
【输入】str：输入的被操作字符串 sub_str：需要查找并删除的特定子字符串
【输出】result_str：在str字符串中删除所有sub_str子字符串后的结果
【返回】删除的子字符串的个数
1 #define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4
5
6 int Mysubstring(char* str_in, char* str_sub, char* str_out)
7 {
8 int start = 0; /* 记录开始比较下标 */
9 int count = 0; /* 记录子串个数 */
10 int j = 0; /* 记录子串的下标 */
11 int k = 0; /* 记录结果字符串的下标 */
12
13 for (int i = 0; str_in[i] != ' '; i++)
14 {
15 start = i; /* 临时保存比较下标 */
16 j = 0; /* 每次开始比较的时候，子串都从0开始,如果第一个字符相等，
17 那么就接着比较下一个字符，否则进入下一轮循环 */
18
19 while ((str_in[i] != ' ') && (str_sub[j] != ' ') && (str_in[i] == str_sub[j]))
20 {
21 i++;
22 j++;
23 }
24
25 if (str_sub[j] != ' ') /* 如果不是子串 */
26 {
27 str_out[k++] = str_in[start]; i = start; /* 将当前比较的这个字符存入结果 */
28 }
29 else /* 如果是子串 */
30 {
31 count++;
32 i--; /* 因为返回for循环之后，进行下一次循环的时候还要进行i++的运算的 */
33 }
34 }
35
36 return count;
37 }
38
39
40 int main()
41 {
42 char* str_in = "i want to be a excellent programmers ";
43 char* str_sub = "want";
44 char str_out[100] = { 0 };
45
46 int count = Mysubstring(str_in, str_sub, str_out);
47
48 printf("子串：%s
", str_sub);
49 printf("个数：%d
", count);
50 printf("原串：%s
", str_in);
51 printf("结果：%s
", str_out);
52
53 return 0;
54
55 }