1

重複の可能性:
文字マトリックスから可能な単語のリストを見つける方法 [Boggle Solver]

私は次のようなString[][]配列を持っています

h,b,c,d
e,e,g,h
i,l,k,l
m,l,o,p

ArrayList で指定された単語を見つけるには、ArrayList をこの配列と照合する必要があります。単語を検索するときは、正の一致と文字の位置を取得する必要があります。helloたとえば、この場合は(0,0)、、、(1,1)およびです。(2,1)(3,1)(3,2)

文字ごとに移動し、最初の文字を見つけることに成功したと仮定するとl、プログラムはその隣の場所で次の文字 ( ) を見つけようとしますl。したがって、e、e、g、k、o、l、m、および i に対して一致する必要があります。これは、その周囲のすべての文字 (水平、垂直、斜め) を意味します。単語内で同じ位置を 2 回見つけることはできないため(0,0)、位置が 2 回一致するため(1,1)、、、、および(2,1)は受け入れられません。この場合、斜めの位置が許可されているため、両方が単語と一致しますが、位置を複数回使用できないという要件により、別の単語と一致する必要があります。(2,1)(3,2)(2,1)l

この場合も一致する必要があります

h,b,c,d
e,e,g,h
l,l,k,l
m,o,f,p

を検索しようとするとhelllo、一致しません。または一致しないかのどちら(x1, y1) (x1, y1)かです。(x1, y1) (x2, y2) (x1, y1)

この種の機能を実装するための最良の方法は何かを知りたいです。ArrayList に4x4String[][]配列と 100,000 ワードがある場合、これを行う最も効率的で簡単な方法は何ですか?

4

4 に答える 4

2

おそらく、グリッドでは構築できない単語を一致させるために、ほとんどの時間を費やすことになると思います。したがって、私が最初に行うことは、そのステップをスピードアップすることです。

文字でインデックスを付けた可能な動きのテー​​ブルとしてグリッドを再表現します。各文字に数字を割り当てることから始めます (通常、A=0、B=1、C=2、... など)。あなたの例では、あなたが持っている文字のアルファベットを使用しましょう（最後の行が「 mofp 」と書かれている2番目のグリッドで）：

 b | c | d | e | f | g | h | k | l | m |  o |  p
---+---+---+---+---+---+---+---+---+---+----+----
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

次に、特定の文字遷移が利用可能かどうかを示す 2D ブール配列を作成します。

     |  0  1  2  3  4  5  6  7  8  9 10 11  <- from letter
     |  b  c  d  e  f  g  h  k  l  m  o  p
-----+--------------------------------------
 0 b |     T     T     T  T     
 1 c |  T     T  T     T  T
 2 d |     T           T  T
 3 e |  T  T     T     T  T  T  T
 4 f |                       T  T     T  T
 5 g |  T  T  T  T        T  T  T
 6 h |  T  T  T  T     T     T  T
 7 k |           T  T  T  T     T     T  T
 8 l |           T  T  T  T  T  T  T  T  T
 9 m |                          T     T
10 o |              T        T  T  T
11 p |              T        T  T
 ^
 to letter

次に、単語リストを調べて、単語をトランジションに変換します (これを事前に計算できます)。

hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10

次に、テーブルでそれらを検索して、これらの遷移が許可されているかどうかを確認します。

[6][3] : T
[3][8] : T
[8][8] : T
[8][10] : T

それらがすべて許可されている場合、この単語が見つかる可能性があります。

たとえば、「ヘルメット」という単語は、4 番目のトランジション (m から e: helMEt) で除外できます。これは、テーブルのエントリが false であるためです。

最初の (h から a への) 遷移は許可されていないため (テーブルには存在しません)、ハムスターという単語は除外できます。

ここで、削除しなかった残りの単語については、現在行っている方法で、またはここの他の回答のいくつかで提案されているように、実際にグリッドでそれらを見つけてみてください. これは、グリッド内の同一文字間のジャンプに起因する誤検知を回避するためです。たとえば、「ヘルプ」という単語はテーブルでは許可されていますが、グリッドでは許可されていません

あなたのボグル電話アプリが完成したら教えてください！;)

于 2012-11-10T22:53:52.010 に答える
0

調査する1つのアプローチは、グリッドから文字（文字列）の可能なすべてのシーケンスを生成し、グリッドに対して各単語をチェックするのではなく、各単語がこの文字列のセットに存在するかどうかをチェックすることです。たとえばh、最初のグリッドから開始します。

h
hb
he
he // duplicate, but different path
hbc
hbg
hbe
hbe // ditto
heb
hec
heg
...

これは、シーケンスを生成するオーバーヘッドがあるため、非常に大きな単語リストの場合にのみ高速になる可能性があります。単語の小さなリストの場合、グリッドに対して個別にテストする方がはるかに高速です。

パス全体（座標を含む）を保存するか、一致する単語のパスを計算するための別の手順を実行する必要があります。どちらが速いかは、ヒット率（つまり、グリッドで実際に見つけた入力単語の割合）によって異なります。

達成する必要があることによっては、シーケンスを辞書の単語のリストと比較して、照合を開始する前に非単語を削除することができます。

リンクされた質問の更新2には、グリッドからシーケンスを生成し、再帰的に深くしてより長いシーケンスを生成する、実用的で高速なソリューションがいくつかあります。ただし、単語リストから生成されたTrieに対してこれらをテストします。これにより、シーケンスのサブツリーを早期に破棄できます。これにより、検索が削除され、効率が大幅に向上します。これは、Markusによって提案された遷移フィルタリングと同様の効果があります。

于 2012-11-10T22:09:00.513 に答える
0

学術的にこの質問に対する美しく効率的な答えがあると確信していますが、同じアプローチを使用できますが、リストの可能性があります。したがって、「こんにちは」という単語の場合、「h」の文字を見つけたら、次に「e」の文字を追加します。すべての可能性が文字のパスを形成します。

于 2012-11-10T22:14:27.917 に答える