Show problems as
Classic problem #1268MediumArrayStringBinary SearchTrieSortingHeap (Priority Queue)

Search Suggestions System

Real-world version: Prefix Hints for the Parts Catalogue
Tracked in this browser only
Read Search Suggestions System on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A stores terminal holds codes, the part codes it stocks, all of them different and written in lowercase letters. A clerk looks a part up by typing typed one letter at a time, left to right.

After each letter the terminal offers hints: the part codes that begin with everything typed so far. At most three are offered, and when more than three codes qualify the terminal offers the three that come first in dictionary order. The hints in a single offer are listed in dictionary order too, and an offer with no qualifying code is empty.

Return one list of hints per letter typed, in the order the letters were typed, so the result holds exactly typed.length lists.

Examples

Example 1

Input
codes = ["bolt", "boltcap", "bo", "brace", "band"], typed = "bol"
Output
[["band", "bo", "bolt"], ["bo", "bolt", "boltcap"], ["bolt", "boltcap"]]

After "b" four codes qualify, so the first three in dictionary order are offered. After "bo" the qualifying codes are "bo", "bolt" and "boltcap". After "bol" only "bolt" and "boltcap" qualify.

Example 2

Input
codes = ["nut"], typed = "nuts"
Output
[["nut"], ["nut"], ["nut"], []]

The single code qualifies for "n", "nu" and "nut", and nothing in the catalogue begins with "nuts", so the last offer is empty.

Example 3

Input
codes = ["washer", "wedge", "well"], typed = "we"
Output
[["washer", "wedge", "well"], ["wedge", "well"]]

After "w" all three codes qualify and are listed in dictionary order. After "we" the code "washer" no longer qualifies.

Constraints

  • 1 <= codes.length <= 1000
  • 1 <= codes[i].length <= 3000
  • 1 <= sum of codes[i].length <= 2 * 10^4
  • The part codes are all different.
  • codes[i] holds only lowercase English letters.
  • 1 <= typed.length <= 1000
  • typed holds only lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def prefix_hints(codes: list[str], typed: str) -> list[list[str]]:
Java
public List<List<String>> prefixHints(String[] codes, String typed)

More on the same topics