Longest Prefix Match Routing
01 · Problem
A router stores a table of routes, each given as a binary string prefix in the array routes (the route's index is its position in the array). An address, also a binary string, matches a route when the route is a prefix of the address (a route longer than the address never matches).
For every address in addresses, return the index of the matching route with the longest prefix. Since all routes are distinct, at most one route of each length can match, so the answer is unique. If no route matches, return -1 for that address.
Return the answers as an array in the same order as addresses.
02 · Examples
routes = ["1","10","101","0"], addresses = ["1011","1100","0001"]
[2,0,3]
"1011" matches "1", "10" and "101"; the longest is "101" at index 2. "1100" only matches "1" (index 0). "0001" matches "0" (index 3).
routes = ["11","011"], addresses = ["10","0110","111"]
[-1,1,0]
"10" starts with neither route. "0110" starts with "011" (index 1). "111" starts with "11" (index 0).
03 · Constraints
- 011 <= routes.length <= 104
- 021 <= routes[i].length <= 32
- 031 <= addresses.length <= 104
- 041 <= addresses[j].length <= 32
- 05routes[i] and addresses[j] consist only of '0' and '1'; all routes are distinct
04 · Optimal complexity
- Time
- O((r + q) * L)
- Space
- O(r * L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.