3

私はちょうどこの質問に出くわしました.文字の2D配列と有効な単語の生のリストが与えられた場合、ブルートフォース以外のより良いアプローチは考えられませんでした. 1) 配列からすべての有効な単語を見つけます。配列内の各要素から、上下左右にトラバースできます。例えば、

g o d b o d y
t a m o p r n 
u i r u s m p

上記の 2D 配列からの有効な単語 -> god、goat、godbody、amour、....

4

3 に答える 3

1

有効な単語のアルファベット順のリストがあることを確認してください。これは、nlgn時間で作成できます。

これで、このソートされたリストができました。文字のシーケンスがlgn時間で正しい単語の始まりであるかどうかを確認できます。

一連の有効な単語を使用して、文字のシーケンスが有効な単語であるかどうかを検証します（一定時間内）。

次に、すべての開始位置に対してgetWords（input、startX、startY、new ArrayList（）、 ""）を呼び出し、結果のリストをマージします。

public List<String> getWords(char[][] input, int x, int y, List<String> result, String current){
    if(isValidWord(current))
         result.add(current);

    if(isValidStartOfWord(current)){
         // call getWords recursively for all valid directions, concatenating the char to current
    }

    return result;
 }

このようにして、O（x ^ 2 * y ^ 2 * lg w）時間で答えを見つけることができます。文字配列のxとyの次元、および有効な単語リストのサイズがあります。それは最悪の場合（lg wの検証を考えると）よりも良くはありませんが、それは私には不可能のようです。予想される実行時間は、この方法の方が優れています。

有効な単語のリストが少ない場合は、正しい単語のすべての有効な開始のセットを作成することもできます。その場合、正しい単語に向かっているかどうかを一定時間で確認でき、最悪の場合はO（x ^ 2 * y ^ 2）になります。

幸運を。

于 2013-02-05T10:20:16.867 に答える
1

プレフィックス ツリーに対して 2D 配列でブルート フォース検索を使用するよりも、このリストをプレフィックス ツリーに前処理する必要があります。

すでに処理された配列のパスや単語部分の同様の入力に対してメモ化を使用することもできます

メモ化の例:

RecursiveMatch(i,j,wordPart)

 if ((i,j,wordPart) in cache) 
   print cache[i,j,wordPart]
   return;
 if a[i,j] on the prefixTreePath){
   cache[i,j,wordPart]+=RecursiveMatch(i+1,j,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i-1,j,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i,j+1,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i,j-1,wordPart[1:])
   print cache[i,j,wordPart]
 }

境界線などのエンド ケースは追加していません。簡単に追加できます。私の意図は、あなたに一般的な考えを与えることでした。

于 2013-02-05T10:02:41.137 に答える
0

1 つのアルゴリズムは、プレフィックス ツリーまたはツリーと呼ばれる適切なデータ構造に依存します。

最初のステップは、有効な単語の辞書を前処理し、それらをトライに入れることです。これにより、次のような質問に効率的に答えることができます。

指定されたプレフィックスは有効なプレフィックスですか?

この質問にはO(lenght of the prefix)、トライを使用して時間内に答えることができます。

次に、単語の開始正方形を選択したとします。ここで、グリッドを 4 方向にトラバースし、これまでに取得したプレフィックスが有効なプレフィックスであるかどうかを確認する必要があります。そうでない場合は、この方向にさらにトラバースすることはありません。一方、これまでのプレフィックスが有効な単語である場合は、それを印刷できます。トラバースは、DFS または BFS のいずれかを使用して実行できます (実際には関係ありません)。重要な部分は、トライを使用して、有効な接頭辞と有効な単語をすばやく確認することです。

于 2013-02-05T10:05:39.533 に答える