0

私はJavaの学校のプロジェクトを持っていて、私も割り当てられています。今、私は理解できないプロジェクトの一部に問題があります。アプリケーションは、2 次元の char 配列 (char[][] ボード) から可能なすべての単語の組み合わせ (辞書で確認できます) を生成する必要があります。ユーザーがスケールを選択できるため、ボードは動的です: 4x4、5x5、4x5、5x4、4x6、... したがって、ネストされたループはここでは適切ではないと思います。間違っている場合は修正してください。単語は、水平、垂直、斜めに生成する必要があります。4x4 ボードの例:

| | あなた | | | あなた | s |

| | n | n | 私 | 私 |

| | | | o | e | b |

| | e | あなた | e | z |

    Code was completely wrong.

もう 1 つのアイデアは、ボード上の可能なすべてのパスをブルート フォースし、それらの保存されたパスを試して、それが単語かどうかを確認することです。

前もって感謝します！

4

3 に答える 3

2

これを解決する1つの方法は次のとおりです。

for each path on the board
    if corresponding word in dictionary
        print it

すべてのパスを見つけるために、任意のグラフ走査アルゴリズムを適応させることができます。

そのサイズのボードには非常に多くのパスがあるため、これは非常に遅くなります（n個のセルを持つボードの場合、最大でn * 4 ^ (n - 1)パスを使用できるため、5 x 5のボードの場合、25*のようなものになります。 2 ^ 50〜= 10^16パス。

これを改善する1つの方法は、グラフのトラバースと辞書のチェックをインターリーブし、現在のパスの単語が辞書の単語のプレフィックスでない場合は中止することです。

class Board {

    char[][] ch;
    boolean[][] visited;

    Trie dictionary;

    void find() {
        StringBuilder prefix = new StringBuilder();
        for (int x = 0; x < maxx; x++) {
            for (int y = 0; y < maxy; y++) {
                walk(x, y, prefix);
            }
        }
     }

    void walk(int x, int y, StringBuilder prefix) {
        if (!visited[x][y]) {
            visited[x][y] = true;
            prefix.append(ch[x][y]);

            if (dictionary.hasPrefix(prefix)) {
                if (dictionary.contains(prefix)) {
                    System.out.println(prefix);
                }

                int firstX = Math.max(0, x - 1);
                int lastX = Math.min(maxx, x + 1);
                int firstY = Math.max(0, y - 1);
                int lastY = Math.min(maxy, y + 1);
                for (int ax = firstX; ax <= lastX; ax++) {
                    for (int ay = firstY; ay <= lastY; ay++) {
                        walk(ax, ay, prefix);
                    }
                }
            }

            prefix.setLength(prefix.length() - 1);
            visited[x][y] = false;
        }
    }

ご覧のとおり、メソッドwalkはそれ自体を呼び出します。この手法は再帰として知られています。

そのため、効率的なプレフィックスクエリをサポートする辞書のデータ構造を見つける必要があります。そのような最良のデータ構造はTrieです。残念ながら、JDKには実装が含まれていませんが、幸いなことに、実装を作成するのは難しくありません。

注：この回答のコードはテストされていません。

于 2013-01-20T22:22:00.477 に答える
0

単純な繰り返し方法を使用して、行、列、および対角線を文字列に変換することから始めます。次に、それを StringBuilder に変換するか、どの単語が本物であるかを確認し、StringBuilder から直接ではない単語を削除します。次に、それを String に出力するだけです。Java の単語を削除または置換するための便利なツールがたくさんあります。

于 2015-03-10T12:02:31.453 に答える
0

これを概念化するかなり簡単な方法は、幅優先検索(BFS) アプローチを各位置に適用することです (または、後で行う微調整に応じて深さ優先)。これにより、検索の最大深度に等しい文字レベルまで、可能なすべての文字の組み合わせが得られます。許可される最長の単語、最大実行時間などの要件に応じて、データ構造またはファイルを介して辞書が提供される場合、これが重要な部分になる場合があります。

または、さらに最適化する必要があるかもしれません。その場合は、BFS または DFS のいずれかを促進する方法を検討してください。DFS を行ったが、"zzz" で始まる単語がないという 3 つの文字を知っていたとしたら? 考えられるすべての注文をたどる必要がないため、多くの時間を節約できます。単語を効果的に検索するには、さらに調整が必要になる場合があります。しかし、Java の組み込み機能 (この例では String.startsWith() が思い浮かびます) から始めて、パフォーマンスを測定し (おそらく、最大ワード長を制限して)、必要なときと場所を最適化します。

于 2013-01-20T19:01:04.703 に答える