Route Pattern Matcher
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
All strings in routes are registered in the order given. A route is a slash-separated path. A segment is either a literal string or a named parameter written as {name}. A parameter segment matches exactly one non-empty URL segment.
For each string in urls, find the first registered route that has the same number of segments and whose literal segments match exactly. If no route matches, return an empty row.
For a match, return one row containing the matched route first, followed by alternating parameter names and values in their left-to-right order: [route, name1, value1, name2, value2, ...]. A literal route therefore produces a one-element row.
Return one row for every URL, in input order.
Function
matchRoutes(routes: String[], urls: String[]) → String[][]Examples
Example 1
routes = ["/users/{id}/pictures/{pictureId}","/health"]urls = ["/users/101/pictures/1","/health","/users/1"]return = [["/users/{id}/pictures/{pictureId}","id","101","pictureId","1"],["/health"],[]]The first URL matches the parameterized route and extracts two values. The second matches the literal route. The final URL has too few segments, so it has no match.
Example 2
routes = ["/files/{name}","/{kind}/{id}"]urls = ["/files/report","/orders/7"]return = [["/files/{name}","name","report"],["/{kind}/{id}","kind","orders","id","7"]]The first registered matching route wins. The second URL does not match the literal files segment, so it uses the fully parameterized route.
Constraints
1 <= routes.length, urls.length <= 10000- The combined length of all route and URL strings is at most
300000. - Every route and URL starts with
/, contains no empty segment, and has no trailing slash. - Each parameter occupies an entire segment, uses a unique lowercase name within its route, and is written as
{name}. - Literal matching is case-sensitive.