algorithm - 在 O(n^2) 中重建省略空格的字符串

Question

我想检查我的算法是否正确。

给定一个 n 个字符的字符串，所有空格都被省略，

Ex: "itwasthebestoftimes"

给出一个动态规划算法，该算法确定字符串是否可以分解为有效的单词序列，并在 O(n²) 中重建一个包含空格的有效字符串。

我的想法:

首先找出一个字符串的所有子串(O(n²))，对每个子串映射其在空间中的位置和长度为一个区间。

Ex:  "it was the best"
      [] [-] [-] [--]
       [---]  []    
          []

(添加空格以使其更易于查看)。

在上面的例子中，“it”是有效的并且得到一个区间值 2，“was”得到 3，等等。字符串“twas”也是有效的，并且得到一个值 4。

然后将其简化为一个 mini-max 问题，以找到间隔集中的最大非重叠长度。由于有效字符串必须包含所有字母，因此最大长度的非重叠区间将是答案，找到它需要 Theta(n*log(n))。

因此该解决方案需要 O(n² + n*log(n)) = O(n²)

我的想法对吗？

Answer 1

您的想法很好(假设您知道找到最大非重叠间隔集问题的 O(n log n) 解决方案)，并且您知道一种在 O(n^ 2)时间。但是，我认为这个问题比你做的要容易。

创建数组 W[0...n]。 W[i] 如果无法将 i 之后的字符串分割成单词，则为 0，否则它将存储开始有效单词的长度切割字符串。

然后:

W[i] = min(j such that W[i:j] is a word, and i+j = n or W[i+j]>0)
       or 0 if there's no such j.

如果您将字典保存在一个特里树中，您可以在 O(n-i) 时间内计算 W[i] 假设您已经计算了 W[i+1] 到 W[n-1]。这意味着您可以在 O(n^2) 时间内计算所有 W。或者如果字典中单词的最大长度是 k，则可以在 O(nk) 时间内完成。

一旦你计算了所有的 W，当且仅当 W[0] 不为 0 时，整个字符串才能被分割成单词。