2
私はJavaで一般的な文字辞書のスペースと時間の効率的な実装を作成しようとしています。時間と空間の効率的な辞書の実装
辞書は、AZから発注されるのではなく、文字 "A"、 "B"などを含むすべての単語をグループ化します。アプリケーションは、ユーザーが入力した文字を含むすべての単語を削除できる必要があります。したがって、ユーザが「L」を入力すると、「L」を含むすべての単語が削除されます。
私が作成している：
設定<文字列>辞書 - 店舗すべての単語を。
マップ<文字セット<文字列>> - 文字AからZをマップします。各文字セットには、その文字を含む辞書のすべての単語が含まれます。
例：
dictionary {"AAB", "ABB", "BBC", "BBA", "CBB"}
マップ：ユーザーが「A」を選択した場合
A - "AAB", "ABB", "BBA"
B - "AAB", "ABB", "BBC", "BBA", "CBB"
C - "BBC", "CBB"
、Aの組が辞書から除去され、マップが再構築され、削除するようにユーザを待っ別の手紙。
私の問題は、これが膨大なデータの重複と非効率を招くことです。私はこれを効率的に実装する別の方法を考えることはできません。私は、木はこれを解決する方法かもしれないと示唆されていますが、その実装がより効率的になる方法を見ることはできません&スペース。
ご協力いただきありがとうございます。
と思われます。同じ文字列オブジェクト（単語）がすべてのセットから参照されるため、重複はありません。また、セットの代わりにリストを使用してオーバーヘッドを減らすこともできます。 – unbeli
ツリーを使用し、各データノードはその下のノードのリストを含んでいます。 AB、AC、AA、ADの下にAノードがあります。このようにすべてのA単語をブロックするには、単にAノードを削除します。すべてのAD単語を除外し、ADノードを削除します。あなたはこれをコードする必要がありますが、それは効率的でなければなりません。 – Sheriff
基数ツリー？ http://en.wikipedia.org/wiki/Radix_tree – maximdim