今日、弟が私に質問をしました。質問は次のとおりです。
Given a list of strings & string M28K, where M28K represents a string which starts
from M, ends with K and has 28chars in between . Find if M28K is unique in the
list of strings or not?
問題の解決策を見つけるために、次のアルゴリズムを思いつきました。
文字列ごとに：
find string length(L)
if(L==30) then
if(str[0]=='M' && str[L-1]=='K') then
verify rest of 28 characters are matching or not
このソリューションは、時間の複雑さの点で効率的ではないようです。誰かがこの問題を解決するためのより良いアルゴリズムを与えることができますか？
私はハッシュで行きます。通常、これはアルゴリズムの宿題の問題のように聞こえるため、私の経験では、実際にはハッシュ関数に依存しているため、ハッシュで答えることができませんでした。十分でない場合、各文字列に対して一意の値を取得できません。
文字列の文字に基づいて、文字列のリストをバイナリ ソート ツリーに構築します。文字列がアルファベット順でヘッド ノードの前にある場合は左側に配置し、ヘッド ノードの後にある場合は右側に配置するというアルゴリズムを維持します。もちろん再帰的に。木があります。最悪の場合、これは O(n) 時間で完了します。これは事実上リンクされたリストになりますが、m または n 領域のどこかに適切なヘッドノードがあれば、このルックアップは O(log n) で完了できます。 . したがって、操作全体には O(n log n) の時間がかかります。
提供されたアルゴリズム、最悪の場合は O(n^2) かかります。すべての文字列が 30 文字で、K で終わり、L で始まるとします。最後の 2 番目の文字を除くすべての文字列です。事実上、提供されたすべての文字列の 28 文字を検索します。n^2 は、すべての文字列のサイズを見つけるのに役立ちます。各文字列は O(n) 時間かかり、n^2 アルゴリズムになります。私のアルゴリズムでは、毎回問題を半分にしています。これにより、検索が大幅に高速化されます。