これは最も一般的に聞かれるインタビューの質問の1つですが、私は効率的な方法でそれを解決することはできません。適切なデータ構造）。 問題は次のようになります。 文字のm x n matrix（haystackと言う）と長さkの文字列char（針）がある場合。干し草に針が含まれているかどうかを確認するプログラムを作成します。干し草を上から下、または左から右へと検索する必要があることに注意してください。 例2つの小さな「干し草」の「針」を検索
Haystack
ahydsfd
sdflddl
dfdfd
dfdl
uifddffdhc
Needle:
hdffi
Output:
Yes Found!!
ナイーブブルートフォースはO（m * n * k）です。最適化のためのアイディアがいくつかあります。
シングル検索
代わりの水平位置を検索して、その後、別の業種のため、同時に両方を行います。あなたが針の最初の文字の出現を見つけるたびに、その文字から始まる水平および垂直の一致を探します。これは複雑さを改善するものではありませんが、多くの場合、悪いスタートを一度しか見ないので、時間が半分になる可能性があります。
レア文字の代わりに、針の最初の文字を探しているの
、針で発生たぐいまれな文字を探します。これは可能性のあるマッチの多くを除外します。どの文字が稀であるかを判断するには、ボード全体をスキャンするか、ランダムサンプリングを使用します。
効率的な文字列などKnuth–Morris–Prattなどstring searching algorithmより良いを使用し
を検索します。アルゴリズムを使用して、各行と各列を個別に検索します。私は、面接者がO（m * n）に複雑さを減らすので、これが面接官の後であるということです。
は私がいないすべての行が同じ長さを持っていることに気づくショート行
を悪用します。垂直方向のマッチを探すときは、針が袋から飛び出すとすぐにその行の検索を止めることができます。これは、さらに行に沿ったすべての針も袋から出て一致しないためです。
スキャン全体で最も希薄な文字を決めるということは、ほとんどの場合、ほとんどの場合、最も多くの作業であるすべてのセルを訪れることです。ほとんどの場合、例えば ' - d'だけを含むボードを除き、針はd大部分は「d」で構成されています。しかし、テキストについてのさらなる知識（文字の分布、言語xのテキストからの文字トークンなど）がなければ、テキストの分析には、単に作業を開始するよりも時間がかかることがあります。行列のサイズがわからない限り、100文字のランダムサンプルでも使用できない場合があります。それが代表的なものであるかどうかはわかりません。 –
のために強引な方法は、針が単一の文字であり、我々は賢明なマトリックス行賢明または列を解析開始した場合のm *のn.Thatの最悪時間計算量がある必要があります。
もちろん、needleの長さがx文字の場合、（m-x-1）* nの複雑さを持つように最適化できます。 – mawia
長い針に問題があります。 –
最初の文字の検索をn-k列とm-k行に制限することができます。いったん見つかると、答えに2（k-1）の比較が必要になります。
左から右へのアリを上から下に別々に検索すると何が問題になりますか？ –
私は2回連続の面接者から、より良いアプローチがあると言われました。私は確信していません、彼らがどのような意味で "より良い"かを意味します。 – hytriutucx
@ javacoder990：あなたは面接官に何を意味するのか尋ねなかったのですか？ –