小编Pet*_*Pet的帖子

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

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

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