これはインタビューの質問です。
名前で構成されるファイルが与えられた場合、名前がリストに含まれているかどうかを検証するためにどのデータ構造を使用しますか? ファイル内の名前との違いが 1 文字以内であれば、その名前は有効であると言う場合はどうなるでしょうか?
これはインタビューの質問です。
名前で構成されるファイルが与えられた場合、名前がリストに含まれているかどうかを検証するためにどのデータ構造を使用しますか? ファイル内の名前との違いが 1 文字以内であれば、その名前は有効であると言う場合はどうなるでしょうか?
ファイルの名前をトライまたはDAWGに保存することをお勧めします(スペース効率が向上します)。名前が到着したら、データ構造のトラバースを開始します。4つのバリエーションがあります。
最初の質問(正確な検索)には、ハッシュテーブルまたはトライを使用できます。ブルームフィルターは、スペースオーバーヘッドで以前に「いいえ」と表示する場合がありますが、明確な「はい」を表示することはできません。
2番目の質問(あいまい検索)では、はるかに高度な手法が必要です。この問題のさまざまな解決策については、 http://blog.srch2.com/2012/03/fuzzy-search.htmlのブログを確認してください。
それは文脈によると思います。何百万もの名前があり、履行する契約があり、それを実行する製品がある場合は、それを選び、自分で書くことは忘れてください.
ただし、インタビューの質問のコンテキストでは、考えられるすべての間違いを含むDAWGを提案します。
かなり前に、スペルチェッカーには (有効な単語のリストと照合するのではなく) 間違いの可能性のある単語のリストが含まれていると聞きましたが、それがどの程度正しいかはわかりません。
私は、単語のリストから (間違いのある) 単語を見つける問題に取り組んだことがありますが、それは 1 つの間違いに限定されたものではなく、多くのメモリを利用できるわけではありませんでした。そのため、単語は単純にリストとして格納されました (DAWG にはノードとポインターが必要であり、オーバーヘッドが大きすぎます)。