用动态编程将字符串拆分为单词

Question

在这个问题中，我们必须将字符串拆分为有意义的单词。我们给了一本字典来看看这个词是否存在。

我“已经在这里看到了一些其他的方法在How to split a string into words. Ex: "stringintowords" -> "String Into Words"?。

我想到了一个不同的方法，并想知道是否会工作或没有。

例 - itlookslikeasentence

算法

字符串的每个字母对应于DAG中的节点。

初始化布尔数组t o错误。

在每个节点上我们都有一个选择 - 如果将当前字母添加到前一个子数组中仍然会生成一个有效的单词，那么将其添加，如果不存在，则我们将从该字母开始一个新单词并设置bool [ previous_node] = True表示一个单词在那里结束。在上面的例子中，bool [1]将被设置为true。

这是类似的最大子阵列和问题。

这个算法能工作吗？

Answer 1

不，它不会。你的解决方案在每一步都会用到最长的单词，但这并不总是奏效。

这里是反例：

让我们假设给定的字符串是aturtle。你的算法将花费a。那么它将采取t作为at是有效的字。 atu不是一个字，所以它会分割输入：at + urtle。但是，无法将urtle拆分为一系列有效的英文单词。正确的答案是a + turtle。

其中一个可能的正确解决方案使用动态编程。我们可以定义一个函数f，使得f(i) = true iff可以将输入的第一个i字符分割成有效的单词序列。最初，f(0) = true和其余的值是false。如果s[l + 1, r]是所有有效的l和r的有效字，则从f(l)到f(r)的转换。

P.S.其他类型的贪婪算法也不适用于此。例如，如果使用最短的单词而不是最长的单词，则无法工作，例如输入atnight：在删除a后无法拆分tnight，但at + night显然是有效的回答。