用動態編程將字符串拆分爲單詞

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顯然是有效的回答。