搜索算法輸入未知

我需要一種算法，將搜索的數組，字符串，但該字符串可能不完全一樣的數組中的項目之一。例如，搜索算法輸入未知

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

這將需要認識到堆棧和樁號都匹配的參數，然後選擇其中一個是第一按字母順序排列。我該怎麼做？

來源

2013-05-10 user2368735

循環數組排序結束後，計算每串和目標串之間的Levenshtein distance，如果它足夠小，回報。

什麼構成「足夠小」取決於你。你可能不得不做一些測試。

來源

2013-05-10 05:14:05 Cairnarvon

它看起來像OP只關心找到第一個部分匹配; Levenshtein距離可能是矯枉過正。 – 2013-05-10 05:36:33

只需通過陣列中的每個元件循環並將其與輸入的，確定所述輸入包含在元件。刪除任何不符合此先決條件的元素。最後通過其餘的元素並選擇第一個按字母順序排列的元素。

來源

2013-05-10 05:15:39 Bacaa14

如果您首先對數組進行排序，則可以在找到第一個匹配項時返回。 – Cairnarvon 2013-05-10 05:17:38

誠然，感謝您的優化！ – Bacaa14 2013-05-10 05:21:49

另外，如果數組已排序，則可以執行二進制搜索。當你在尋找幾個可能的匹配中的第一個時，有點棘手，但是如果有足夠的興趣，我有一個實現。 – 2013-05-10 05:37:42

循環通過陣列的所有索引值和找到輸入的字符串匹配。查找所有匹配項並打印索引值最低的那個。

例如，你會發現陣列[0]和數組子字符串匹配[3]。現在您在0和3處有兩場比賽。找到下一場比賽的下一個字母。在Arrary [0]中，Sta的下一個字母爲'c'，但在Array [3]處，下一個字母爲'k'，這裏是< k，所以輸出是Array [0]

來源

2013-05-10 05:16:03

您可能會發現Trie數據結構有用。找到你需要的所有單詞是非常有效的。

但是，如果列表中有許多單詞，則內存開銷可能很大。

來源

2013-05-10 06:14:24 sergtk

我會使用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.

您可以在列表中做二進制搜索，如果叮Search的結果是> 0，則存在鍵您的列表中，否則（-x-1）插入時是關鍵的位置。轉到以輸入字符串開頭的每個元素。

例如，編曲是陣列，並且您正在搜索的輸入。

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是數組的長度。

來源

2013-05-10 06:31:31 smttsp

搜索算法輸入未知

回答

相關問題