問題タブ [prefix-tree]

私は C++ プログラムと私のグループに取り組んでいますが、inOrder トラバーサルを使用してプレフィックス コードを生成する方法についてのロジックを理解できません。PrefixCode ツリーが構築されており、そこからコードを生成したいと考えています。

ロジックに問題があるため、コードを提供する必要があるかどうかわかりません。必要な場合はお知らせください。

ありがとう。

配列に NSStrings があります。

検索文字列を渡して、必要なすべての文字列を見つけたいと考えています。たとえば、「ax」を渡すと 3 つの文字列が返され、「axx」を渡すと 2 つの文字列が返されます。

ここでもパフォーマンスが重要です。メソッドは次のようになります。

通常は を使用NSPredicateしますが、今回はおそらくプレフィックス ツリーまたはバイナリ ツリーを使用する必要があります。実装への提案またはリンク。

2 つの異なる XSD から 2 つのクラスを取得しました。そのうちの 1 つはその子ノードです。ルート クラスには子のプロパティ (xmlelement 配列) があり、子ノードに異なるプレフィックスを付ける必要があります。これは私のコードです:

次に、ルートをシリアル化します。

XML ファイルは正しい形式で作成されましたが、子ルートには名前空間があり、そこには必要ありません。ルート ノードでのみ必要です。

トライで特定のプレフィックスを検索することは O(M) で行われることを知っています。ここで、M はトライに挿入される任意の単語の最大長です。

しかし、特定のプレフィックスで始まるすべての要素を取得する時間の複雑さはどのくらいでしょうか?

私は可能な答えについて考えました：

O(M+n) ここで、n はプレフィックスで始まる単語の数です。アイデア: プレフィックスの検索は O(M) にあります。次に、指定されたプレフィックスで始まるすべての単語を含むサブトリーがあり、それをトラバースするだけです。問題 (おそらく): プレフィックス ツリーに単語より多くのノードがあります。しかし、私がそれらを見る必要がないように、何らかの形の効率的な保存があるのではないでしょうか?

ここで説明されているキーボードのオートコンプリートの問題を解決しようとしています。 問題は、いくつかの辞書とオートコンプリートのルールが与えられた場合に、単語に必要なキーストロークの数を計算することです。たとえば、辞書の場合:

次の結果が得られます (詳細については、上記のリンクを参照してください)。

簡単な説明: ユーザーがを入力するhと、eで始まるすべての単語は2 番目の文字hも持つため、オートコンプリートされます。eユーザーが を入力するlと、もう一方lが塗りつぶされ、 という単語が 2 ストロークになりますhell。もちろん、helloもう 1 ストローク必要です。その他の例については、上記のリンクを参照してください。

私のTrieコードは次のとおりで、正常に動作します ( https://en.wikipedia.org/wiki/Trieから取得)。コードは、Stackルートからツリーを解析することです (以下の編集を参照)。

ストローク数を数える方法がわかりませんでした：

そして、ルートからツリーを解析するコードは次のとおりです。

どんなアイデアや建設的なコメントも役に立ちます、ありがとう!

編集

@SergiyKolesnikovによるすばらしい答え。への呼び出しを避けるためにできる小さな変更が 1 つありますendsWith()。Trie クラスにブール値フィールドを追加しました。

そして、insert() の最後に:

curr.value.endswith('$'):次に、に置き換えるだけcurr.eowです。皆さん、ありがとうございました！

私のハッシュ コードは、単語のタイトル全体のみを返します。少なくとも 2 単語 (以降) のキーワードのみを使用して結果を表示し、結果を表示する (get 関数) ようにしたいと考えています。

私のハッシュコード

サンプル出力:

タイトル全体が入力されたとき

キーワードが入力されたとき (キーワードが入力された場合でも結果を表示する必要があります)

必要なもの