FastPrepCount Prefix Matches in a Sorted Array
Problem · String

Count Prefix Matches in a Sorted Array

Learn this problem
● MediumGoogle logoGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

Problem statement

Given a lexicographically sorted array of lowercase strings words and a lowercase string prefix, return the number of array entries that begin with prefix.

Duplicate words count separately. For this exercise, assume all words and the prefix are non-empty and use ordinary lowercase lexicographic order.

Use the sorted order to locate the contiguous matching range with binary search.

Function

countPrefixMatches(words: String[], prefix: String) → int

Examples

Example 1

words = ["apple","apply","apt","banana"]prefix = "app"return = 2

Only apple and apply begin with app.

Example 2

words = ["a","a","ab","b"]prefix = "a"return = 3

Both copies of a and the word ab match, so duplicates contribute separately.

Constraints

  • 0 <= words.length <= 2 * 10^5
  • Every word and prefix is a non-empty lowercase English string.
  • words is sorted in nondecreasing lexicographic order.
  • The total number of characters in words and prefix is at most 2 * 10^5.

More Google problems

drafts saved locally
public int countPrefixMatches(String[] words, String prefix) {
    // Write your code here.
}
words["apple","apply","apt","banana"]
prefix"app"
expected2
checking account