arrays - 入力が不完全な検索アルゴリズム

Question

配列で文字列を検索するアルゴリズムが必要ですが、文字列は配列内の項目の 1 つと完全に同じではない可能性があります。例えば、

Array = {"Stack", "Over", "Flow", "Stake"}
input = "Sta"

Stack と Stake の両方がパラメーターに一致することを認識し、アルファベット順で最初のものを選択する必要があります。これどうやってするの？

Answer 1

List を使用し、そのリストで binarySearch を実行します。

List<String> arr = new ArrayList<>();

要素を追加します。要素を追加しながら、次のことができます。

int x = Collections.binarySearch(arr, key); 
if(x < 0)
    arr.add(-x-1, key);
//for n element this takes n.log_n time.

リストでバイナリ検索を実行できます。binarySearch の結果が > 0 の場合、キーはリストに存在します。それ以外の場合 (-x-1) は、キーが挿入されたときの場所です。入力文字列で始まる各要素を真にします。

たとえば、arr が配列で、入力を検索しているとします。

arr = {"Flow", "Over", "Stack",  "Stake"}
input = "Sta";

int x = Collections.binarySearch(arr, input);
if(x < 0)
    x = -x-1;

if(arr.get(x).subString(0,input.length()).equals(input));
    System.out.println(arr.get(x))
else 
    System.out.println("there is no element starting with input string");

時間計算量は O(logn) で、n は配列の長さです。

Answer 2

並べ替えられた配列をループし、各文字列とターゲット文字列の間のレーベンシュタイン距離を計算し、それが十分に小さい場合は戻ります。

「十分に小さい」を構成するものはあなた次第です。おそらく、いくつかのテストを行う必要があります。