I'm pretty sure it's number 2, as the prefix search requirement is probably the reason why they went with the linear search in the first place, and didn't just

I'm pretty sure it's number 2, as the prefix search requirement is probably the reason why they went with the linear search in the first place, and didn't just use a hash map.