1

文字の 2D 行列が与えられた場合、与えられた単語がその中に存在するかどうかを確認する必要があります。例えば

 s f t 
 d a h 
 r y o

その中に「ラット」を見つけることができます （トップダウン、ストレート、ダイアゴナル、または任意のパス）..逆の順序でも.最小限の複雑さで.

私のアプローチは

While traversing the 2d matrix ( a[][] ) row wise. 
If ( a[i][j] == first character of given word ) { 
    search for rest of the letters in 4 directions i.e. right, right diagonally down, down and left diagonally down. 
} else if( a[i][j] == last character of the given word ) { 
    search for remaining characters in reverse order in 4 directions i.e. left, right diagonally up, up, left diagonally up. 
}

より良いアプローチはありますか？

4

4 に答える 4

2

この問題に対する非常に優れたデータ構造について説明しましょう。

さあ、Tries を調べてみてください。

長さ k の単語をトライに挿入するには O(k) 時間、長さ k の単語の存在を調べるには O(k) の時間がかかります。

ビデオチュートリアル

データ構造の理解や実装に問題がある場合は、喜んでお手伝いします。

于 2013-06-23T15:43:39.887 に答える
0

実際、ここには 16 のシーケンスがあります。

sft
dah
ryo
sdr
fay
tho
sao
rat
tfs
had
oyr
rds
yaf
oht
oas
tar

(水平 3 + 垂直 3 + 対角 2) * 2 (反転) = 16. n を行列のサイズとします。あなたの例では n = 3. シーケンスの数 = (n + n + 2) * 2 = 4n + 4.

次に、シーケンスが単語かどうかを判断する必要があります。(インターネットで見つけた) 辞書の単語を使用してハッシュ セット ( unordered_setC++ ではHashSetJava) を作成します。O(1) で 1 つのシーケンスを確認できます。

于 2013-06-23T15:25:47.873 に答える
0

私はこれを2つの段階で行うと思います：

1) 単語の最初の文字のインスタンスを探して、配列を反復処理します。

2) 最初の文字のインスタンスを見つけるたびに、隣接するすべてのセル (たとえば最大 9 個) を調べる関数を呼び出して、それらのいずれかが単語の 2 番目の文字であるかどうかを確認します。2 番目の文字の一致が見つかった場合、この関数はそれ自体を再帰的に呼び出し、それに隣接するセルで 3 番目の文字の一致を探します (など)。再帰が単語の最後の文字まで到達し、一致するものが見つかった場合、その単語は配列に存在します。(文字を 2 回使用することが許可されていない場合は、アルゴリズムがセルを再利用するのを防ぐために、セルに「既に使用されている」というフラグを付ける必要があることに注意してください。おそらく、これを行う最も簡単な方法は pass-再帰関数への使用済みセル座標のベクトルの値渡し、

于 2013-06-23T15:37:54.893 に答える
0

単純なループを使用して最初の文字または単語を探し、見つかったら次の再帰関数を使用します。

この関数は、入力 5 つのパラメーターとして取得します: 探している単語、配列内で探してstrいる単語内の文字の現在の位置、および文字と方向を検索するための配列内の位置として。strkijd

停止条件は次のとおりです。

-もしもk > strlen(str); return 1;

-もしもarr[i][j] != str[k]; return 0;

上のステートメントのいずれも真でない場合は、文字カウンターをインクリメントしますk++。の値に応じてiandを更新し、関数を再度呼び出しますjdreturn func(str, k);

于 2013-06-23T15:51:25.553 に答える