算法-删除字符串中的公共字符

墨蓝 2022-06-10 09:22 333阅读 0赞

**题目：**  
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入“They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”

**解题思路：**  
好未来那这道题做过笔试题目，首先最简单的思路就是两层循环遍历，下面将“They are students.”称为字符串1，将“aeiou”称为字符串2。每遍历到字符串2中的一个字符，就在字符串1中找到相同的字符，找到之后删除它，并将字符串1后面的字符整体向前移动1位。所以这个过程的时间复杂度是O(n^3)，下面我们就可以考虑如何优化它了：

**1.如何解决顺序存储结构中删除后整体移动的问题？**  
假设当前遍历到字符串2中的“a”，现在遍历字符串1，要求是是“a”的话就删除，那么这个要求换一个思路就是不是“a”就保留，在不申请新的空间的情况下，我们只需要把要保留的字符覆盖字符串中1原来的字符，要删除的字符不做覆盖，此时就需要有两个指针，一个在控制整体的遍历过程，一个记录要插入的位置：  
![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
可以看到，在遍历的过程中，如果没有出现要删除的字符的话，p1和p2一直在同步走（同步走的过程也是要覆盖的过程，一直在用p1的指向字符覆盖p2，只是他们指向相同，覆盖也就没有意义了），而出现了要删除的字符，p2会停下来，指示p1指向的字符要覆盖的位置，这样的话，我们就能避免每一次删除后的整体平移，这样的话时间复杂度还有O(n^2)。

**2.如何避免两层遍历的嵌套？**  
O(n^2)的时间复杂度是由遍历两个字符串产生的，能否应用一些方法避免循环嵌套的问题，引入hash表。  
两个遍历嵌套的过程无非是为了找到字符串2中的字符在字符串1中是否出现，那么如果我们对字符串1建立hash表，在遍历字符串2时就可以根据hash索引直接找到要删除的字符，这样的话时间复杂度就可以降到O(n)，下面考虑字符串2中出现重复字符的情况，无所谓啊，反正都是要删了的。  
所以我们就能对字符串2建立一个hash表了，hash函数选择：`(int)arr2[n]`。在字符串2中出现的字符，在hash表中的值为1，未出现的字符表值为0。  
hash表范围的选取：  
a ：97  
A ：65  
z ：122  
Z ：90  
标点符号还在字母之前，所以hash范围选成256就足够了。  
所以总的来说，我们用一个O(256)的空间复杂度，将时间复杂度从O(n^2)将为O(n)，所以如果n很大的话，这个替换是值得的。

**代码实现：**

#include "iostream"    
    
    using namespace std;
    void  DeleteChar(char arr1[],char arr2[]);
    int main()
    {   
      char str1[] = "They are students.";
      char str2[] = "aeiou";
      cout<<str1<<endl;
      DeleteChar(str1,str2);
      cout<<str1<<endl;
      getchar();
      return 0;
    }
    void  DeleteChar(char *arr1,char *arr2)
    {
        if(arr1 == NULL && arr2 == NULL)
            return;
        //创建hash表
        int hash_table[256] = { 0 };
        char *p1 = arr1;
        char *p2 = arr2;
        int index =0;
        //遍历删除串
        while(*p2 != '\0')
        {
            hash_table[(int)*p2] = 1;
            p2++;
        }
        //遍历待删除串
        while (*p1 != '\0')
        {
            //该字符不需要删除
            if( 0 == hash_table[(int)*p1] )
            {
                arr1[index]= *p1;
                index++;
            }
            p1++;
        }
        arr1[index]='\0';
    }

[SouthEast]: /images/20220610/d0bd0f635b814cb687580b67ec2f1276.png
[SouthEast 1]: /images/20220610/84e36e47aa4f4a3ab2734da1e115dd51.png