Finding entries in a TreeSet that contain a prefix
java, string, treeset
Solution
If one String `foo` is a prefix of another String `bar` in the TreeSet, I believe it is a safe assumption for `bar` to immediately follow `foo` in the TreeSet.
Thus, I believe it suffices to take `TreeSet.ceiling(foo)` and check whether `foo` is a prefix of it.
From the documentation of that function, we see that it returns exactly the element that would follow the given element in order.
Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
The algorithm would thus be :
- Call `TreeSet.ceiling()` on the input. If the return value is `null`, then return `false`.
- If the return value is not `null`, return whether the input is a valid prefix of the return value.
Problem
I have a TreeSet in Java that contains Strings (specifically words). I need to write a method... `public boolean isValidPrefix(String prefix)` ...which accepts a prefix as an argument and checks the TreeSet to see if any of its contained words begin with the prefix. For example, given the prefix "CA" and a TreeSet containing {"DOG,"CAT","COW"}, my method would need to identify that there is a word "CAT" which starts with the prefix. P.S. I would iterate through the TreeSet, but time complexity is an obvious constraint as the TreeList will be up to 200,000 words in many instances.