Prefix Search II
You are given words, sorted ascending (duplicates allowed), and a prefix. Return the inclusive range [first, last] of the indexes of the words that start with prefix, or [-1, -1] if none do. Aim for O(log n) string comparisons.
words = ["ap", "app", "apple", "apple", "aq"] prefix "app" => [1, 3] prefix "b" => [-1, -1] prefix "" => [0, 4] (every word starts with "")
Up to 10^5 words of lowercase a-z, lengths up to 100.
Hints
Hint 1
The matches are contiguous, and the first one is lower_bound(prefix) — if the word there starts with prefix at all.
Hint 2
Every match sorts strictly below the prefix with its last character incremented ("ap" -> "aq"). lower_bound on that bumped string, minus one, is the last match.
Hint 3
The empty prefix has no last character to bump — it matches the whole list.