文字列から最長の単語を見つけることができるかどうかを尋ねる問題を見つけたとき、私はいくつかのアルゴリズムの問題に取り組み始めました（文字列には文字だけのスペースがありません）。しばらく考えた後、最大連続和問題と同様に、この問題に動的計画法を使用できるかどうかを確認したかっただけです。ここで、すべての文字を解析した後、isWordメソッド（すでに実装されています）を呼び出すことができます。次の文字に進み、単語の長さを増やす場合は、カウンターをゼロにリセットして、そのインデックスから単語を探し始めます。 。それが良いアプローチであるかどうかを教えてください。そうでない場合は、これを解決するためのより良いアプローチを教えてください。
助けてくれてありがとう。
-Vik
このアルゴリズムは正しく機能しません。次の文字列について考えてみます。
BENDOCRINE
文字列の先頭から始めて、まだ単語が残っている間に前方にスキャンすると、「BEND」という単語が見つかり、その後文字列をリセットしてOからピックアップします。ここでの正しい答えは、代わりにピックすることです。はるかに長い「ENDOCRINE」という言葉。
静的辞書があり、その辞書からテキスト文字列に含まれている最長の単語を検索する場合は、Aho-Corasickアルゴリズムを確認することをお勧めします。、テキスト文字列内の文字列のセットのすべての一致を検索し、非常に効率的に検索します。アルゴリズムを簡単に変更して、出力した最長の単語をいつでも追跡し、これまでに見つかった最長の文字列よりも短い文字列を出力しないようにすることができます。この場合、実行時間はO（n + m）になります。 nは検索するテキスト文字列の長さであり、mはすべての有効な英語の単語の文字の総数です。さらに、事前にO（m）前処理を行うと、その時点から、時間O（n）で特定の文字列内の最長の単語を見つけることができます。ここで、nは文字列内の文字数です。
（時間内に実行される理由O（n + m）：通常、実行時間はO（n + m + z）です。ここで、zは一致の数です。出力される一致の数を制限して、これまでの最長ワードよりも短いワードの場合、最大でnワードが出力される可能性があります。したがって、実行時間はO（n + m + n）= O（n + m））です。
お役に立てれば！
動的計画法はあなたの問題では機能しません：
seq1とseq2を2文字のシーケンスとします
isWord（Concatenation（seq1、seq2））は、isWord（seq1）とisWord（seq2）の値から推測できません。