4

特定の単語が辞書内の他の単語の始まりになるかどうかを調べる必要があります。

TreeSet を使用して辞書を実装しました。

TreeSet ディクショナリ文字列 startString;

問題1

startString開始点が少なくとも辞書に載っている単語かどうかを調べる最も効率的な方法は何ですか?

アイデア1

私の考えは使用することですdictionary.subSet(startString, startStringPlusOne);

は、アルファベットの次の文字である最後の文字を除いてstartStringPlusOne等しいです。startString

例：

startString: hom
startStringPlusOne: hon

このようにしSubSetて空のセットを返します。これはstring、辞書内の単語の先頭ではないことを意味します。

問題 2

stringPlusOne を計算する最も効率的な方法は何ですか?

アイデア2

文字の配列をアルファベット文字で使用し、最後の文字をstring配列内の次の文字に置き換えることを考えました。より効率的な方法はありますか？

4

1 に答える 1

1

メモリに問題がなければ、2 つの辞書を保存したくなるでしょう。あるものにはあなたの言葉を入れ、別のものにはあなたの言葉の始まりを入れます。

1)
["aardvark", "banana", "band"]

2)
{
    "aardvar" => 1,
    "aardva" => 1,
    "aardv" => 1,
    "aard" => 1, 
    "aar" => 1, 
    "aa" => 1, 
    "a" => 1, 
    "banan" => 1, 
    "bana" => 1, 
    "ban" => 2, 
    "ba" => 2, 
    "b" => 2
}

では、「ban」から始まる言葉はありますか？は「はい、2つあります」です。あなたの質問は、それらがどの単語であるかを見つける必要があるかどうかを述べていません。

カウントは、辞書から単語を削除する必要がある場合にのみ役立ちます。その場合、カウントをデクリメントし、キーが 0 になったらキーを削除する必要があります。これを行う必要がない場合は、数値を保存する必要はありません。

「「ban」で始まる単語はどれですか?」という質問に答える必要がある場合は、カウントだけでなく、それらの単語への参照を保存する必要があります。

"ban" => ["banana", "band"]

これは、速度の点で最も効率的であるように思われますが、メモリの点で効率が低下します (心配する価値はないかもしれません)。

于 2013-01-23T16:26:23.350 に答える