使用动态编程将字符串拆分为一串有效字

Question

我需要找到一个动态编程算法来解决这个问题.我试过但无法弄明白.这是问题所在:

您将获得一个n个字符串[1 ... n],您认为这是一个损坏的文本文档,其中所有标点符号都已消失(因此它看起来像"itwasthebestoftimes ...").您希望使用字典重建文档,该字典以布尔函数dict(*)的形式提供,对于任何字符串w,如果w是有效字,则dict(w)的值为1,并且值为0除此以外.

1. 给出动态编程算法,确定字符串s [*]是否可以重构为有效字序列.运行时间应该至多为O(n ^ 2),假设每次调用dict都需要单位时间.
2. 如果字符串有效,请使算法输出相应的单词序列.

Answer 1

让压缩文档的长度为N.

设b(n)为布尔值:如果文档可以从文档中的位置n开始分割成单词,则为true.

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)设置为true.如果没有这样的单词,则将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是从算法的第一部分生成的布尔数组.

Answer 2

正式确定@MinhPham建议的内容.

这是一个动态编程解决方案.

给定一个字符串str,让

b [i] =如果子串str [0 ... i](包括)可以分成有效的单词,则为真.

将一些起始字符添加到str,比如说!来表示空字.str ="!" + str

基本情况是空字符串,所以

b [0] =真.

对于迭代案例:

b [j] =如果b [i] == true且str [i..j]是所有i <j的单词,则为真

Answer 3

字符串 s[] 可能会被分割成不止一种方式。下面的方法找到我们可以分割 s[] 的最大单词数。下面是算法的草图/伪代码

bestScore[i] -> 存储前 i 个字符可以分割的最大单词数（否则为 MINUS_INFINITY）

for (i = 1 to n){
     bestScore[i] = MINUS_INFINITY
     for (k = 1 to i-1){
        bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k))
     }
 }

其中 f(i,k) 定义为：

f(i,k) = 1 : if s[i-k+1 to i] is in dictionary
       = MINUS_INFINITY : otherwise

bestScore[n] 将存储 s[] 可以拆分的最大单词数（如果值为 MINUS_INFINIY，则 s[] 无法拆分）

显然运行时间是O(n^2)

由于这看起来像教科书练习，因此我不会编写代码来重建实际的分割位置。