arrays - 输入不完整的搜索算法

Question

我需要一种算法，它将在数组中搜索字符串，但该字符串可能与数组中的一项不完全相同。例如，

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) 是插入时该键的位置。go tru 每个以输入字符串开头的元素。

例如， 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

循环排序数组，计算每个字符串与目标字符串之间的Levenshtein 距离，如果足够小，则返回。

什么构成“足够小”取决于您。您可能需要进行一些测试。

Answer 3

只需遍历数组中的每个元素并将其与输入进行比较，确定输入是否包含在元素中。删除任何不满足此先决条件的元素。最后浏览剩余的元素并选择按字母顺序排列的第一个元素。

Answer 4

循环遍历数组的所有索引值并找到输入的子字符串匹配。找到所有匹配项并打印索引值最低的匹配项。

例如，您会发现 Array[0] 和 Array[3] 的子字符串匹配。现在您在 0 和 3 处有两个匹配项。找到子匹配项的下一个字母。在 Arrary[0] 下一个到 Sta 的字母是“c”，但在 Array[3] 下一个字母是“k”，这里 a < k，所以输出是 Array[0]

Answer 5

您可能会发现Trie数据结构很有用。找到您需要的所有单词非常有效。

但是如果列表中有很多单词，内存开销可能会很大。