Effectively get a subset of "startWith" strings from a set

Question

I have a large set of strings, and I want to create an autostart function for it.

Suppose the set ["foo", "fighter"]

The input "f" should return both values, and the input "fo" should only return "foo" .

I am currently just iterating through a set and outputting the results, calling startsWith , however this is too slow.

The standard TreeSet with its subset functions will not help here, since it only implements the RB tree.

Is there an effective solution in the Java API or do I need to create my own implementation of Set ?

---

Edit: My implementation looks like this using Andrei Nayumenko tri datastructures . Note to increase the size of the array if you want to use extended ASCII characters. If you use List instead of Map , you get the results in sorted order.

 public Set<String> getSubset(String s) { result = new HashSet<String>(); getSubset(root, s); return result; } private void getSubset(TrieNode node, String s) { TrieNode n = node; for (char ch : s.toCharArray()) { if (n.children[ch] != null) { n = n.children[ch]; continue; } return; } getSubsetR(n, s); } private void getSubsetR(TrieNode node, String s) { for (char ch = 0; ch < node.children.length; ch++) { TrieNode child = node.children[ch]; if (child != null) getSubsetR(child, s + ch); } if (node.leaf) { result.add(s); } } 

Answer 1

What you are looking for is a prefix tree data structure: http://en.wikipedia.org/wiki/Trie

The code here will help you: https://sites.google.com/site/indy256/algo/trie