algorithm - T9 辞書を実装するには?

Question

モバイルで使用される辞書をどのように実装できますか? （モバイルでメッセージを入力するときに使用されます）。入力した文字で形成できる単語のリストを表示します。

例：

4663は良い、なくなった、家に帰ることができます。

467 提案された単語が重要として表示されます。

Answer 1

簡単な解決策は、事前に単語を計算し、ノードに数字を持つトライツリーを構築することです。各リーフノードには、それらを使用して形成できる文字列のリンクリスト/配列(またはその他のデータ構造)へのリンクがあります。数字。

任意の時点で、たとえば、ユーザーが 4663 と入力した場合 -> null ではない最後のノード (例では数字 3 を持つ) のすべての子に移動し、さまざまなパスを介してリーフ ノードに到達し、有効な単語を出力します。

注 : 桁数が 10 しかないため、トライ ツリーのサイズは制限されます。トライ ツリーの代わりに 3 分探索ツリー (TST) を使用することもできますが、ここでは 10 桁しかないため、TST を使用する利点はあまりありません。

EDIT - user1168577 が指摘したように、使用頻度のようなヒューリスティックを使用して、単語をその順序で表示できます。