У меня большой набор URL, и я хочу реализовать автозаполнение. Мне не нравится сложность наивного подхода, так как он линейный с заданным размером:

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

Теперь я знаю, что в хэш-наборе функция "contains ()" работает в "O (1)", но нет "containsPrefix ()". Есть ли простой способ без использования большой библиотеки, такой как Lucene, или написания кода самостоятельно? У меня не было бы проблем с этим, но это кажется излишним для такой простой проблемы, поэтому я хочу знать, существует ли существующее простое решение :-)

Из своих уроков информатики я помню дерево, которое состоит из фрагментов строк, но я забываю, как оно называлось. Это сработало так:

[car, care, carrot,carrotville]->

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

П.С .: Как мне вызвать методы, которые возвращают все строки, префиксом которых является строка? Например, если a является префиксом b, что такое b для a?