1. 概要

このチュートリアルでは、2D文字マトリックスからすべての可能な単語のリストを見つける問題について説明します。

まず、問題を定義し、2D文字マトリックスで単語を取得します。 次に、それを説明するための例を示します。 最後に、この問題を解決するための2つの異なるアプローチを紹介し、それらの実装と時間計算量を処理します。

2. 問題の定義

2D文字マトリックスがあり、そのマトリックスから取得できるすべての可能な単語を生成するように求められたとします。

最初に、単語は2Dマトリックスのパスで表されます。ここで、指定された単語の最初の文字を含むセルから開始し、現在の1つの隣接する8つのセルで2番目の文字を探します。 言葉の終わりに達するまで動き続けます。 結局、単語を取得するためにたどるルートは、異なる位置にある必要があります（同じセルを複数回使用することはできません）。

次の例を見てみましょう。 次の2D文字マトリックスがあるとします。

、、、、などの複数の有効な単語を取得できます。 たとえば、前のマトリックスから単語を取得する方法を見てみましょう。

ご覧のとおり、隣接するセルのシーケンスを取得し、同じセルを2回取得しないことで、単語を取得します。 最後に、前の例の結果は、指定された2Dマトリックスから形成される可能性のあるすべての有効な単語のリストになります。

3. 素朴なアプローチ

3.1. 本旨

このアプローチの主なアイデアは、指定されたマトリックスで可能なすべてのパスを試すことです。 各パスが有効な単語を作成するかどうかを確認します。

まず、単語が有効かどうかを定義する単語の辞書があります。 次に、指定されたマトリックスの各セルに対して backtracking メソッドを実行し、現在のセルから始まる指定されたマトリックス内のすべての可能なパスを生成します。

次に、セルに到達するたびに、そのセルを現在のパスに追加し、訪問済みセルとしてマークして、再度考慮しないようにします。 次に、それがすべてのパスに対して有効な単語を形成するかどうかを確認します。 もしそうなら、与えられた行列から生成される可能性のある単語のsetにそれを追加します。 それ以外の場合は、それを無視して他のパスをチェックします。

最後に、指定された行列から生成されたすべての可能な有効な単語のリストを取得します。

3.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、指定された行列内のすべての可能な有効な単語を生成する関数を宣言します。 関数には4つのパラメーターがあります。 とは、指定されたマトリックス内の現在の位置を表し、現在までに持っている現在の単語を表し、指定されたマトリックスから生成されたすべての可能な有効な単語を表します。

まず、現在のセルの文字をに追加し、現在のセルに訪問済みのマークを付けます。 次に、辞書内のすべての可能な有効な単語を繰り返し処理して、現在の単語が有効かどうかを確認します。 一致するものが見つかった場合は、のセットに追加します。

次に、隣接する8つの隣接セルに移動する遷移配列を宣言します。 それぞれについて、指定された行列の境界内にあり、まだアクセスされていないかどうかを確認してから、そこに移動して関数を呼び出します。

最後に、現在のセルの文字をさかのぼって未訪問としてマークし、将来使用できるようにします。

指定された行列の各セルから関数を実行すると、そのセルから生成される可能性のあるすべての有効な単語がセットに含まれます。 これらのセットを組み合わせると、指定された2D文字マトリックスから生成されたすべての単語が提供されます。

3.3. 複雑さ

このアルゴリズムの時間計算量はです。ここで、は指定された行列のセル数であり、は辞書内のすべての単語の長さの合計です。 この複雑さの背後にある理由は、セルごとに次のセルの可能性が異なり、可能性ごとに、辞書内のすべての有効な単語を繰り返し処理して、現在の単語と一致するかどうかを確認するためです。

関数がグリッド内の各セルから呼び出される場合、複雑さは、になります。ここで、およびは行列の行と列の数です。

4. トライアプローチ

4.1. 本旨

このアプローチの主なアイデアは前のアイデアと同じですが、trieデータ構造を使用して現在の単語を辞書の単語と照合する複雑さを最適化します。

まず、すべての辞書の単語を含むトライデータ構造を作成して、単語が一定時間有効かどうかを確認します。 次に、各セルからバックトラック関数を実行し、そのセルで始まるすべての可能な単語を生成します。

次に、セルごとに、現在の単語がトライ構造内にあるかどうかを確認します。 もしそうなら、私たちはそれを可能な単語のセットに追加します。 次に、訪問していない隣接セルに移動して、他の有効な単語を検索しようとします。

最後に、可能な単語セットには、指定されたマトリックスから生成できるすべての単語が含まれます。

4.2. トライ構造の構築

辞書からトライ構造を作成する実装を見てみましょう。

辞書のすべての単語を含むトライ構造を作成する関数を宣言します。この関数は、言語で使用可能なすべての有効な単語のリストを表す1つのパラメーターを取ります。

最初に、指定された辞書のすべての単語を格納するトライ構造のを宣言します。 次に、辞書の各単語を繰り返し処理して、トライ構造に挿入します。

最後に、辞書のすべての単語を含むトライ構造のを返します。

4.3. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初は、以前と同じ関数に1つのパラメーターが追加されています。これは、すべての可能な有効な単語を持つトライ構造のルートを表します。

まず、現在の文字がトライ構造内の現在のノードの子の1つではないかどうかを確認します。つまり、現在の文字を取得できません。 そこで、バックトラック機能に戻ってブレークします。 それ以外の場合は、現在の文字を持つの子に移動します。

次に、前のアプローチと同じプロセスを実行します。 ただし、現在の単語の有効性を確認するために、trie構造を使用して、現在の単語が一定時間内に有効かどうかを確認します。

その後、隣接する8つのセルすべてで関数を呼び出します。

最後に、セットには、開始位置から生成される可能性のあるすべての有効な単語が含まれます。 各セルからこの関数を呼び出すと、考えられるすべての単語のリストが表示されます。

4.4. 複雑

このアルゴリズムの時間計算量はです。ここで、は指定された行列のセル数であり、は辞書内のすべての単語の長さの合計です。 この複雑さの背後にある理由は前のアプローチと同じですが、辞書内のすべての可能な単語を繰り返す代わりに、時間計算量で構築するトライデータ構造を使用して現在の単語を一定時間でチェックします。

関数がグリッド内の各セルから呼び出される場合、複雑さは、になります。ここで、およびは行列の行と列の数です。

5. 結論

この記事では、2D文字マトリックスからすべての可能な単語を見つける問題について説明しました。 まず、問題を説明する例を示しました。 次に、2つの異なるアプローチを検討しましたが、それぞれのアプローチの方が時間計算量が高くなっています。

最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。