搜索算法输入未知

我需要一种算法，将搜索的数组，字符串，但该字符串可能不完全一样的数组中的项目之一。例如，搜索算法输入未知

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

搜索算法输入未知

回答

相关问题