title: How to create a simple prefix index in Java?
body: <p>I have big set of urls and I want to implement an autocompletion. I don't like the complexity of the naive approach as it is linear with the set size:</p>
  
  <pre><code>for(String url: urls) if(url.startsWith(input) {doSomething();}
  </code></pre>
  
  <p>Now I know that in a Hash Set, the function "contains()" works in "O(1)" but there is no "containsPrefix()". Is there a simple way without using a big library like Lucene or coding it myself? I would have no problem doing it but it seems overkill for such a simple problem so I want to know if there is an existing simple solution :-)</p>
  
  <p>From my computer science classes I remember a tree which consists of string fragments but I forget how it was called. It worked like this:</p>
  
  <pre><code>[car, care, carrot,carrotville]-&gt;
  
  car
  |
  -/
  -e
  -rrot
    |
    ----ville
  </code></pre>
  
  <p>P.S.: How do I call the methods that returns all strings that a string is prefix of? Like if a is prefix of b, what is b to a?</p>