string - 删除句子中的片段 [puzzle]

Question

问题:

编写一个程序来删除出现在“所有”字符串中的片段，其中一个片段是 3 个或更多个连续的单词。

示例:

输入:

s1 = "正在下雨，我想开车回家。";

s2 = "下雨了，我想去滑雪。";

s3 = "天气热，我想去游泳。";

输出:

s1 = "下雨开车回家。";

s2 = "下雨了，去滑雪吧。";

s3 = "天气热去游泳吧。";

已删除的片段 = "and i want to"

程序将再次测试大文件。将考虑效率。

假设:忽略大小写、标点符号。但保留在输出中。

注意:注意像

这样的情况

a a a a a b c b c b c b c 其中移除会产生更多碎片。

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

1. 将三个单词短语散列为一个 int 并将它们存储在一个数组中，用于所有字符串。减少为数字数组，如

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

问题简化为数组的交集。

对数组进行排序。 (k * nlogn)

保留k个指针。如果找到所有相等的匹配项。否则增加指向最小值的指针。解决上面的注释。我在想做一个懒惰的删除，即在最后标记要删除和删除的短语。

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

Answer 1

第一个观察:用大字母表中的单个“字母”替换每个单词(即以某种方式散列世界)，删除空格和标点符号。

现在您已将问题简化为删除出现在给定列表的所有 个单词中的最长字母序列。所以你必须计算一组“单词”的最长公共(public)子串。您使用 generalized suffix tree 找到它因为这是最有效的算法。这应该可以解决问题，我相信它具有最好的复杂性。