如何在Java中创建简单的前缀索引？

Question

我有很多网址，并且想实现自动补全功能。我不喜欢朴素方法的复杂性，因为它与设置大小成线性关系：

for(String url: urls) if(url.startsWith(input) {doSomething();}

现在我知道在哈希集中，函数“ contains（）”在“ O（1）”中有效，但是没有“
containsPrefix（）”。是否有一种简单的方法，而无需使用像Lucene这样的大库或自己编写代码？我这样做没有问题，但对于这样一个简单的问题似乎有点过头了，所以我想知道是否存在现有的简单解决方案:-)

从我的计算机科学课程中，我记得一棵由字符串片段组成的树，但我忘记了如何调用它。它像这样工作：

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

PS：如何调用返回字符串作为前缀的所有字符串的方法？就像a是b的前缀一样，b对a是什么？

Answer 1

如果您需要有效地查找字符串的前缀，请使用Trie，这是专门为此目的设计的数据结构：

特里树或前缀树是一种有序的树数据结构，用于存储键通常为字符串的关联数组。与二叉搜索树不同，树中没有节点存储与该节点关联的密钥。相反，它在树中的位置定义了与其关联的键。节点的所有后代具有与该节点关联的字符串的公共前缀，并且根与空字符串关联

两个链接与示例
实现。