algorithm - 删除字符串 S1 中出现在字符串 S2 中的所有字符

Question

给定两个字符串 S1 和 S2，S = S1 - S2 定义为从 S1 中取出 S2 中的所有字符后剩余的字符串。如何尽快计算任何给定字符串的 S1 - S2？

例如:

输入:

他们是学生。

爱你

输出:

你的标准。

我试过hash map，遗憾的是评委说它太慢了，但是有什么解决方案可以更快吗？

这是我的代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool occur[300]={false};
int main()
{
    char str1[10002];
    gets(str1);
    char ch;
    while((ch=getchar())!='\n')
        occur[ch]=true;
    int i;
    for(i=0;i<strlen(str1);i++)
        if(occur[str1[i]])
            continue;
        else
            putchar(str1[i]);
    putchar('\n');
    return 0;
}

Answer 1

我认为你应该:

1. 创建包含 S2 中所有字符的 HashSet S
2. 使用列表，在迭代 S1 时附加不在 S 中的字符
3. 从列表中构建字符串(Python 中的“.join(list..))”

我不认为有更快的方法。您可以将 S1 分成 N 个部分并并行处理 - 这是我看到的唯一优化 ...

至于您的代码 - 不要在循环条件中使用 strlen!参见:strlen: how does it work? .只需遍历所有字符，直到获得 '\0' 字符或计算一次 strlen 并放入您在循环条件中使用的变量 ...