単語が2つの有効な単語で構成されている場合

Question

与えられた単語が辞書内の2つの単語で作成できるかどうかを調べる辞書があります。たとえば。与えられた "新聞"は、それが2つの言葉で作ることができるかどうかを見つけなければならない。 （この場合のニュースと論文）。私が考えることができるのは、始めから始めて、現在の文字列が単語であるかどうかをチェックすることだけです。この場合、n、ne、new、news .....をチェックする。現在の文字列が有効な単語であれば残りの部分をチェックする。

また、kのためにそれを一般化します（単語がk単語で構成されている場合を意味します）。何かご意見は？

Answer 1

私はstrpos（-like）関数を使って辞書をループして、それがまったく起こっていないかどうかをチェックします。結果と一致するものが見つかるかどうか試してください。 、辞書strpos-INGの辞書ですべての単語を、配列に結果を保存して

• ループのは、それは私に結果「新規」、「紙」を与えましょう、と： は、だから、このような何かをするだろう'ニュース'。
• 新しい+紙==新聞か、新しい+ニュース==新聞か、紙になるまで+新しい==新聞が戻るかどうかを確認してください。

しかし、それは良い方法であるかどうかわかりませんが、手紙のために単語の文字をチェックするよりも効率的で、2番目の単語が始まったときをチェックする方法を説明しませんでした。

「あなたはどのようにそれをkのために一般化していますか？」という意味が分かりません。

Answer 2

スプリットを中央で開始すると、結果がより速くなる場合があります。たとえば、新聞の場合は、まず「ニュースペーパー」または「新聞紙」で分割します。ご覧のとおり、この例では、最初または2回目の試行で結果が見つかります。結果が見つからない場合は、外から検索してください。以下の「クロスボウ」のための例を参照してください：二つの単語の場合については

cros sbow 
cro ssbow 
cross bow 

Answer 3

、問題はそれがだかどうかを確認するために各半分をチェックし、ちょうど2つに単語を分割するすべての可能な方法を考慮することによって解決することができます有効な単語。入力文字列の長さがnの場合、文字列を分割する方法はO（n）のみです。高速検索をサポートする構造体に文字列を格納する場合（トライ、ハッシュテーブルなど）

もっと興味深いのは、k> 2ワードで単語を分割する場合です。

単語は、単語に分割してk - 1語に分割することができれば、k個の単語に分割することができます。

再帰的な基本的なケースは、単語がゼロの単語に分割できるのは、それが空の文字列である場合に限られます。

この再帰的な洞察を使用するには、可能なすべての単語の分割を2つの部分に分けて元のアルゴリズムを修正します。分割が完了すると、分割の最初の部分が単語かどうか、分割の2番目の部分がk - 1語に分割できるかどうかを確認できます。最適化として、可能性のあるすべての分割について再帰的に実行するのではなく、最初の単語が有効であることがわかっている分割のみに再帰的に適用します。ここでは、Javaで書かれたいくつかのサンプルコードがあります：それはk個の異なる部分に文字列のすべての可能なパーティションを生成しようとするため

public static boolean isSplittable(String word, int k, Set<String> dictionary) { 
    /* Base case: If the string is empty, we can only split into k words and vice- 
     * versa. 
     */ 
    if (word.isEmpty() || k == 0) 
     return word.isEmpty() && k == 0; 

    /* Generate all possible non-empty splits of the word into two parts, recursing on 
     * problems where the first word is known to be valid. 
     * 
     * This loop is structured so that we always try pulling off at least one letter 
     * from the input string so that we don't try splitting the word into k pieces 
     * of which some are empty. 
     */ 
    for (int i = 1; i <= word.length(); ++i) { 
      String first = word.substring(0, i), last = word.substring(i); 

      if (dictionary.contains(first) && 
       isSplittable(last, k - 1, dictionary) 
       return true; 
    } 

    /* If we're here, then no possible split works in this case and we should signal 
     * that no solution exists. 
     */ 
    return false; 
} 

} 

このコードは、最悪の場合には、（nは^K）時間Oで実行されます。もちろん、ほとんどの可能な分割がすべての単語を形成することはないので、この最悪の場合の動作には当てはまりそうにありません。