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

Question

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

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

我想到了一种不同的方法，想知道它是否有效。

例子- itlookslikeasentence

算法

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

将 bool 数组初始化为 False。

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

这类似于最大子数组和问题。

这个算法行得通吗？

Answer 1

不，不会。您的解决方案在每一步都采用尽可能长的单词，但这并不总是有效。

反例:

假设给定的字符串是 turtle。您的算法将采用 a。然后它将采用 t 作为 at 是有效的词。 atu 不是单词，因此它将拆分输入:at + urtle。但是，无法将 urtle 拆分为一系列有效的英语单词。正确答案是 a + turtle。

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

附言其他类型的贪心算法在这里也不起作用。例如，如果您使用最短的单词而不是最长的单词，它就无法处理输入 atnight:无法在 tnight 之后拆分a 被剥离了，但是 at + night 显然是一个有效的答案。