algorithm - 使用动态规划将字符串拆分为一串有效单词

Question

我需要找到一个动态规划算法来解决这个问题。我试过了，但想不通。这是问题所在:

给你一个包含 n 个字符的字符串 s[1...n]，你认为它是一个损坏的文本文档，其中所有标点符号都消失了(因此它看起来像“itwasthebestoftimes...”)。您希望使用字典重建文档，该字典以 bool 函数 dict(*) 的形式提供，这样，对于任何字符串 w，如果 w 是有效单词，则 dict(w) 的值为 1，而值为 0否则。

1. 给出一个动态规划算法，确定字符串 s[*] 是否可以重构为有效单词序列。运行时间最多为O(n^2)，假设每次调用dict花费单位时间。
2. 如果字符串有效，让你的算法输出相应的单词序列。

Answer 1

让压缩文件的长度为 N。

令 b(n) 为 bool 值:如果文档可以从文档中的位置 n 开始拆分为单词，则为真。

b(N) 为真(因为空字符串可以拆分为 0 个单词)。给定 b(N), b(N - 1), ... b(N - k)，你可以通过考虑以字符 N - k - 1 开头的所有单词来构造 b(N - k - 1)。如果有任何这样的词 w，设置 b(N - k - 1 + len(w))，然后将 b(N - k - 1) 设置为真。如果没有这样的词，则将 b(N - k - 1) 设置为 false。

最终，您计算 b(0)，它告诉您是否可以将整个文档拆分为单词。

在伪代码中:

def try_to_split(doc):
  N = len(doc)
  b = [False] * (N + 1)
  b[N] = True
  for i in range(N - 1, -1, -1):
    for word starting at position i:
      if b[i + len(word)]:
        b[i] = True
        break
  return b

您可以使用一些技巧来使“从位置 i 开始的单词”变得高效，但是您需要 O(N^2) 算法，因此您可以在字典中查找从 i 开始的每个字符串。

要生成单词，您可以修改上面的算法以存储好单词，或者像这样生成它:

def generate_words(doc, b, idx=0):
  length = 1
  while true:
    assert b(idx)
    if idx == len(doc): return
    word = doc[idx: idx + length]
    if word in dictionary and b(idx + length):
       output(word)
       idx += length
       length = 1

这里的 b 是从算法的第一部分生成的 bool 数组。