動的プログラミングで文字列を単語に分割する

Question

この問題では、文字列を意味のある単語に分割する必要があります。単語が存在するかどうかを調べる辞書が用意されています。

私は「ここにHow to split a string into words. Ex: "stringintowords" -> "String Into Words"?で他のいくつかのアプローチを見てきた。

私は別のアプローチを考え、それが仕事をしたりしません場合は思っていた。

例 -

アルゴリズム

itlookslikeasentence

文字列の各文字はDAG内のノードに対応します

ブール配列を初期化するt o偽。

各ノードには選択肢があります。以前のサブアレイに現在の文字を追加しても有効な単語が作成された場合は追加し、そうでない場合は追加してbool [ previous_node] =単語がそこで終わったことを示す真。上記の例では、bool [1]はtrueに設定されています。

これは、最大サブアレイの合計問題に似ています。

このアルゴリズムは機能しますか？

Answer 1

いいえ、そうではありません。あなたは、すべてのステップで最長の単語を取りますが、必ずしもそうではありません。ここで

は反例です：

はのは、与えられた文字列がaturtleであると仮定しよう。あなたのアルゴリズムはaになります。その後が有効な単語であるため、tが必要です。 atuは単語ではないので、入力を分割します：at + urtle。しかし、urtleを一連の有効な英単語に分割する方法はありません。正しい回答はa + turtleです。

可能な正しいソリューションの1つに、動的プログラミングが使用されています。入力の最初のi文字を有効な単語列に分割することができる場合は、f(i) = trueのような関数fを定義することができます。最初はf(0) = trueで、残りの値はfalseです。 lとrのすべての有効な単語がs[l + 1, r]である場合、f(l)からf(r)への移行があります。

P.S.他の種類の欲張りアルゴリズムもここでは機能しません。たとえば、最長の単語の代わりに最短の単語を使用すると、入力がatnightなどでは機能しません。aを切り捨てた後にtnightを分割する方法はありませんが、at + nightは明らかに有効です回答。