時間の複雑さはどうなりますか? これがO(n!)であることを避けたいだけです。深度優先検索を使用すると、時間の複雑さはO(n^2)になりますか?
これについて正しい方法で考えているかどうかはわかりません。
深さ優先検索を使用するとは、最初の文字から深さ優先検索を開始し、次に 2 番目の文字から開始するという意味です。
それは必要ですか？
注:
元の問題は、クロスワード/ボグル ボードですべての可能な単語を見つけることです。単語が辞書にあるかどうかを調べるためにトライ データ構造を使用することを考えていますが、単語自体を生成する方法を考えています。
上記の議論に続いて、ここに私の答えがあります：
定義: atrieXは単語の長さXだけのサブ トライです。
目的の言語ですべての単語を試したので、適切なtrieX.
クロスワード パズルにはw単語があると言うので、配列 long を作成します。ここで、各エントリは、関連する単語の長さでwある trieX のルートです。Xこれにより、各空白単語に含まれる可能性のある単語のリストが得られます。
次に、単語間の交差を反復処理し、配置できない単語を削除します。変更が行われなくなったら、停止します。
2 つの注意事項:
1. パフォーマンスを向上させるために、長い単語または非常に短い単語を追加することから始めます。ショートとロングって何？これとこれを見てください。
2. trieX からの単語の削除は、単語間の依存関係をチェックすることによっても実行できます (THIS 単語がここにある場合、THAT 単語はそこに存在できない、など)。これはもっと複雑なので、これを簡単に行う方法について誰かがアイデアを追加したい場合は、してください。