删除句子中的碎片[拼图]

Question

题:

编写程序以删除在"所有"字符串中出现的片段,其中片段是3个或更多个连续字.

例:

输入::

s1 ="正在下雨,我想开车回家.";

s2 ="下雨了,我想去滑雪.";

s3 ="天气炎热,我想去游泳.";

输出::

s1 ="正在下雨开车回家.";

s2 ="正在下雨去滑雪.";

s3 ="游泳很热.";

删除片段 ="我想要"

该程序将再次测试大文件.效率将被考虑在内.

假设:忽略大写,标点符号.但保留在输出中.

注意:照顾像这样的情况

aaaaabcbcbccc删除会产生更多碎片.

我的解决方案:( 我认为不是最有效的)

1. 将三个单词短语散列成一个int并将它们存储在一个数组中,用于所有字符串.减少到像数组一样

   1 2 3 4 5
   3 5 7 9 8
   9 3 1 7 9
   

问题减少到数组的交集.

排序数组.(k*nlogn)

保持k指针.如果发现所有相等的匹配.否则将指针指向最小值.解决上面的注意事项.我正在考虑做一个懒惰的删除,即在最后标记删除和删除短语.

是否存在我的解决方案可能不起作用的情况？我们能否优化我的解决方案/找到最佳解决方案？

Answer 1

第一步正如 izomorphius 已经建议的那样：

将每个单词替换为大字母表中的单个“字母”（即以某种方式散列世界），删除空格和标点符号。

对于第二个，您不需要知道最长的公共子字符串 - 您只想从所有字符串中删除它。注意，这相当于擦除所有长度恰好为 3 的公共子串，因为如果你有一个更长的公共子串，那么它的长度为 3 的子串也是公共的。为此，您可以使用哈希表（存储键值对）。

只需迭代第一个字符串，并将其所有 3 子字符串作为值等于 1 的键放入哈希表中。然后迭代第二个字符串，对于每个 3 子字符串 x（如果 x 在哈希表中且其值为 1） ，然后将值设置为 2。然后迭代第三个字符串，对于每个 3 子串 x，如果 x 在哈希表中且其值为 2，则将值设置为 3。 ...依此类推。最后，值为 k 的键是公共 3 子串。

现在只需再次迭代所有字符串并删除那些常见的 3 个子字符串。