Pickup Zone Prefix Routing

Longest prefix of each string found in a given list of strings

EasyTriesPrefix Matching

A ride-sharing app assigns dispatch zones short lowercase codes. A pickup label belongs to a zone when the zone's code is a prefix of the label: the label starts with the entire code.

Given the registered zone codes codes and the pickup labels labels, return one string for each label, in the same order. Each string must be the longest registered code that is a prefix of that label. If no registered code matches, return "" for that label.

Repeated registrations of the same code have no additional effect. A code may match an entire label. An empty label never matches a code.

Examples

Example 1

Input: codes = ["n","north","west"], labels = ["northgate","neon","south"]
Output: ["north","n",""]

For the label "northgate", both "n" and "north" match, so the longer registered code is selected. "neon" matches only "n", and "south" has no matching code.

Example 2

Input: codes = ["ca","cab","cabin","cab"], labels = ["cab","cabin","cabinet","car"]
Output: ["cab","cabin","cabin","ca"]

The label "cab" matches a registered code exactly. Although "cabin" begins with "cab", the longer registered code "cabin" takes priority. Repeated registrations do not change the choice.

Example 3

Input: codes = [], labels = ["market",""]
Output: ["",""]

With no registered zones, neither a nonempty label nor an empty label can be routed.

Constraints

  • 0 <= codes.length <= 3000
  • 0 <= labels.length <= 3000
  • 1 <= codes[i].length <= 20
  • 0 <= labels[i].length <= 20
  • All characters in codes and labels are lowercase English letters.
  • Codes and labels may contain duplicates.

Let C be the total length of the registered codes and L the total length of the labels. The intended solution takes O(C + L) time and O(C) auxiliary space, excluding the returned strings.

Hints

Show hint 1

Store registered codes in a trie and mark the nodes where complete codes end.

Show hint 2

For each label, follow its characters through the trie while remembering the most recent marked node.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you support registering and removing codes between label lookups?
  • How would you also return the number of registered distinct codes that match each label?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem