1

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

例如 ：

输入：

他们是学生。

艾欧

输出：

你的标准。

我已经尝试过哈希映射，遗憾的是法官说它太慢了，但是任何解决方案都可以更快吗？

这是我的代码：

#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;
}
4

4 回答 4

2

我想你应该：

  1. 创建包含 S2 中所有字符的 HashSet S
  2. 使用 List 在您遍历不在 S 中的 S1 时将字符附加到该列表
  3. 从列表中构建字符串（Python 中的"".join(list..)）

我认为没有更快的方法..您可以将 S1 分成 N 部分并在此并行上工作 - 这是我看到的唯一优化...

至于您的代码 - 不要在循环条件下使用 strlen ！请参阅：strlen：它是如何工作的？. 只需遍历所有字符，直到您获得 '\0' 字符或计算 strlen 一次并放入您在循环条件中使用的变量...

于 2013-03-10T10:48:00.570 回答
1

如果您可以将问题限制在一个小字母（例如仅英文字符），您可以创建一个与您的字母大小相同的 bool 数组。

1 数组查找将比散列或遍历二叉树快得多。

于 2013-03-10T10:50:49.973 回答
0

可能最快和最简单的方法之一是使用正则表达式替换。请参阅下面的示例 python 代码。

如果不能使用正则表达式，则需要对输入字符串的每个字符进行一个循环。由于您正在处理每个字符，因此任何算法都至少是O(n). 这意味着加快实现速度的唯一方法是减少检查字符是否需要复制到输出以及实际复制到输出所花费的时间。由于我不知道您使用的是什么语言，所以我将在 python 中给出一个简短的实现。set这使用了允许持续时间检查值是否在集合中的 python类。示例代码如下。

import re

def remove1(string, chars):
    return re.sub("[%s]"%chars, "", string)

def remove2(string, chars):
    chars = set(chars)
    res = ""
    for c in string:
        if c not in chars:
            res += c

    return res

import unittest

class TestRemove(unittest.TestCase):
    def test_removeVowels1(self):
        self.assertEqual("Thy r stdnts.", remove1("They are students.","aeiou"))

    def test_removeVowels1(self):
        self.assertEqual("Thy r stdnts.", remove2("They are students.","aeiou"))

if __name__=="__main__":
    unittest.main()

注意：如果您使用像 C++ 这样的语言并且知道输入仅限于 8 位值，那么最快的方法是使用直接寻址；即使用字符值作为数组索引。

于 2013-03-10T12:09:40.097 回答
0

从技术上讲，Hashmap 的解决方案是 O(n)+O(m)，n即句子的长度和m禁止字符的数量。

在我看来，这是您在决定是否保留或丢弃该字符时必须运行的最快速度。此外，您必须至少遍历所有禁止字符一次才能了解它们。

但是，我可以想象有更有效的解决方案，即更少的开销。但老实说，我想不出一个。

更新（这是最简单的，但它是 O(n*m)。但是，它可能比其他短字符串方法更快）：

foreach (c in sentence) 
  if (forbiddenChars.IndexOf(c) == -1) 
    Console.Write(c);
于 2013-03-10T12:12:37.023 回答