cf.completefrontend
ALGORITHMS IN FRONTEND WORK · CORE

Route matching

Decide whether a URL path fits a route pattern like /users/:id, and pull out the named parts, by comparing them segment by segment.

Time O(L)Space O(L)5 practice problemsStep-through picture

The idea

A single-page app shows different screens for different URLs. A router holds a list of patterns, such as /, /users/:id, and /files/*, and for the current path, like /users/42, it finds the matching pattern and the values of its parameters: here { id: "42" }.

Matching works one segment at a time. A segment is the text between two / characters. Split both the pattern and the path on /. A plain segment like users must be equal in both. A segment starting with : is a parameter: it matches any one segment and saves it under its name. A * is a wildcard: it matches everything that is left.

If any plain segment differs, or the path runs out of segments too early, or has extra segments at the end, the route doesn't match. When an app has many routes, the router tries them in a set order or ranks them, so that /users/new wins over /users/:id.

An everyday example

Filling in a form letter

A form letter says "Dear ____, your order ____ has shipped." A real letter matches it if every printed word is the same and each blank holds exactly one word. You read both side by side, word by word. Printed words must agree. Blanks pick up whatever word sits there, and you write it down under the blank's label. If the real letter has extra words or is missing some, it isn't this form.

How the example maps to the code
In the exampleIn the code
The form letterThe pattern, split into patternParts
The real letterThe path, split into pathParts
A printed word that must matchA plain segment like users
A labeled blankA segment like :id, saved into params
"And everything after this"The * wildcard

From the slow way to route matching

  1. Start with the obvious way: compare the path with each route string, path === pattern. That works for /about, but /users/42 would need a separate route for every user, and nothing pulls out the 42.
  2. A regular expression per route fixes that: ^/users/([^/]+)$ matches any user and captures the id. Many routers do turn patterns into regular expressions. But writing them by hand is easy to get wrong, and you still need to connect each captured group to a name.
  3. Look at the shape of a URL path instead: it is a list of segments separated by /. In a pattern, a plain segment like users stands for exactly one segment, and so does a :name segment. So segment i of the pattern can only line up with segment i of the path. There is never a choice to make.
  4. So split both on /, drop empty pieces, and walk them side by side. Plain segments must be equal, :name segments save the path segment under that name, and a final * takes everything that's left. At the end, both lists must have run out together. That walk is route matching.

How it works

  1. Split the pattern and the path on / and drop empty pieces, so leading, trailing, and doubled slashes don't matter. These are patternParts and pathParts.
  2. Walk the pattern's segments with i. If the segment is *, save the rest of the path, joined with /, as params["*"] and return params.
  3. If the path has no segment at i, the path is too short: return null.
  4. If the segment starts with :, save pathParts[i] (decoded with decodeURIComponent) under the name after the :.
  5. Otherwise the segment is plain and must equal pathParts[i]; if not, return null.
  6. After the loop, the path must not have extra segments: return params only if both lists had the same length.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function matchRoute(pattern, path) {
  2. const patternParts = pattern.split("/").filter(Boolean);
  3. const pathParts = path.split("/").filter(Boolean);
  4. const params = {};
  5. for (let i = 0; i < patternParts.length; i++) {
  6. const part = patternParts[i];
  7. if (part === "*") {
  8. params["*"] = pathParts.slice(i).join("/");
  9. return params;
  10. }
  11. if (i >= pathParts.length) return null;
  12. if (part.startsWith(":")) {
  13. params[part.slice(1)] = decodeURIComponent(pathParts[i]);
  14. } else if (part !== pathParts[i]) {
  15. return null;
  16. }
  17. }
  18. return patternParts.length === pathParts.length ? params : null;
  19. }

How fast it is

TimeO(L)
Extra memoryO(L)

Each segment of the pattern and path is looked at once. The split lists and the params object hold at most all the segments.

  • Best caseO(L)

    Even if the first segment differs, both split calls have already read both strings, which costs time in proportion to their length L.

  • Average caseO(L)

    A normal match: split both strings, then compare a handful of segments.

  • Worst caseO(L)

    A full match on a long path: every segment is compared once and parameters are decoded. Trying r routes one after another costs O(r * L).

Common mistakes

  • Matching with startsWith on the whole string. /user then matches /users/42, and /users matches /users-admin.
  • Forgetting the length check at the end. /users/:id would then match /users/42/settings.
  • Not decoding parameters. A name like Ana%20Lima arrives encoded; decode it once, and only the parameter, not the whole path.
  • Relying on route order without thinking. /users/:id listed before /users/new swallows the new page. Order specific routes first, or rank them.

When to use it

Look for these clues in a problem:

  • You match URL paths, file paths, or topic names against patterns with placeholders.
  • The patterns use :name parameters or * wildcards.
  • You must pull named values out of a string that follows a known layout.
  • Several patterns could match and the question defines which one wins.

Check yourself

Answer each one in your head first, then open it.

Why does this matcher never need to back up and try again?

Every plain and :name segment matches exactly one path segment, so there is only one way to line the pattern up with the path. Only a wildcard in the middle would create choices.

What does matchRoute("/users/:id", "/users/42/settings") return?

null. The loop matches users and captures id = "42", but the path has 3 segments and the pattern 2, so the final length check fails.

Why decode parameters after splitting, not before?

An encoded slash, %2F, is part of a value, not a separator. Decoding first would turn it into / and split one value into two segments.

With first-match routing, /users/:id is listed before /users/new. What does /users/new show?

The user page, with { id: "new" }, because :id matches any one segment and comes first. List specific routes first, or rank the routes.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The key fact is the alignment: every plain or :name segment matches exactly one path segment. So if the path matches at all, pattern segment i must match path segment i. There is only one way to line them up, which is why a single left-to-right walk with no going back is enough.

The loop keeps this rule: at the top of loop i, the first i pattern segments matched the first i path segments, and params holds exactly the values captured from them. Each case keeps the rule or gives the right answer early. A plain mismatch returns null. A path that ran out returns null. A parameter matches anything and records it. A * matches all the rest and returns.

The loop ends after patternParts.length steps. If it gets there, every pattern segment matched, so the path matches exactly when it has no extra segments, which is the final length check. One limit follows from the code: * returns at once, so any pattern segments after it are ignored. That's why the wildcard must come last.

Going deeper

3 more ideas

Why segment by segment is enough

A :param matches exactly one segment, and plain segments match exactly one segment. So segment i of the pattern always lines up with segment i of the path. There is no guessing about where a parameter ends, which is why this simple walk is correct. Only the * can match a variable number of segments, and here it is only allowed at the end.

Choosing between several matching routes

/users/new matches both /users/new and /users/:id. Older routers return the first route in the list, so you must order routes carefully. React Router v6 and later rank routes instead: plain segments score higher than parameters, which score higher than *, so the most specific route wins whatever the order.

How fast it is

Splitting and walking take O(L) for a path of length L. Trying r routes one after another is O(r * L). Routers with many routes can store patterns in a trie of segments, so matching only follows one branch per segment.

Work it by hand

Every step in a table, with why

Match a team's file URL with a parameter, an encoded space, a trailing slash, and a wildcard.

pattern = "/teams/:teamId/files/*", path = "/teams/red%20fox/files/specs/q3.pdf/"

StepipartpathParts[i]params afterWhat happensWhy
1-4 parts5 parts{}split and drop empty piecespatternParts is [teams, :teamId, files, *]. The trailing / gives an empty piece, which filter(Boolean) drops, so pathParts is [teams, red%20fox, files, specs, q3.pdf].
20teamsteams{}plain and equalA plain segment must match exactly, and it does.
31:teamIdred%20fox{ teamId: "red fox" }parameter, decodedThe segment starts with :, so it captures the path segment. decodeURIComponent turns %20 into a space.
42filesfiles{ teamId: "red fox" }plain and equalAnother exact match.
53*specsadds "*": "specs/q3.pdf"wildcard: returnThe wildcard joins the rest of the path, from index 3 on, with / and returns at once.

It returns { teamId: "red fox", "*": "specs/q3.pdf" }. The length check after the loop never runs, because the wildcard returned first.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Route matchingO(L)O(L)Patterns with :name and a trailing *, where segment-by-segment rules are all you need.
Compile each pattern to a regular expressionO(L)O(L)You need extras like optional segments or rules on what a parameter may contain. Libraries like path-to-regexp do this; their exact syntax differs between versions.
Try every route in orderO(r · L)O(L)A small app with tens of routes. Simple, but the order of the list decides which route wins.
Segment trieO(L)O(r · L)Hundreds of routes, as on a server, where you want the cost to depend on the path, not the number of routes.

Extra memory: O(L) for the two lists of segments and the params object.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Route matching and the other approaches, on a scale where each line up is 10 times more steps.
  • Route matching, Compile each pattern to a regular expression, Segment trie O(L)
  • Try every route in order O(r · L)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Route matching101,0001 million
Compile each pattern to a regular expression101,0001 million
Try every route in order1001 million1 trillion
Segment trie101,0001 million

Inputs that need care

6 tricky inputs
Trailing or doubled slashes: "/teams//red/"
filter(Boolean) drops the empty pieces, so it gives the same segments as "/teams/red".
The root: matchRoute("/", "/") and matchRoute("/", "/a")
The first has no segments on either side, so the loop doesn't run and the lengths match: it returns {}. The second has an extra path segment, so it returns null.
Nothing after a wildcard: pattern "/teams/:teamId/files/*", path "/teams/red/files"
At i = 3 the path has no segment, but * is checked first, so it returns { teamId: "red", "*": "" }. If an empty wildcard shouldn't match, check for it.
A badly encoded parameter: "/a/%E0%A4%A"
decodeURIComponent throws a URIError. Wrap it in try and treat the error as no match, or the whole router crashes on one bad link.
An encoded slash inside a parameter: "/files/a%2Fb"
The path is split before decoding, so a%2Fb stays one segment and decodes to "a/b". Decoding first would wrongly split it in two.
A query string or different case: "/Teams/red?tab=2"
This code is case-sensitive, so Teams doesn't equal teams, and the last segment would be red?tab=2. Pass location.pathname, not the whole URL. React Router and Express ignore case by default.

Variations and follow-ups

Twists interviewers add

Ranking several matches

/users/new matches both /users/new and /users/:id. Instead of taking the first route in the list, give each pattern a score where plain segments count more than parameters and parameters more than *, and pick the highest. React Router does this, so the order you list routes in doesn't matter.

A trie of segments

With hundreds of routes, put the patterns in a tree with one level per segment. Matching follows one branch per path segment, trying the plain child before the parameter child. Server routers like find-my-way, used by Fastify, use a radix tree like this.

Nested routes

A parent route matches the first few segments and hands the rest to its child routes, which match the remaining segments. This is how layouts with their own child pages work in React Router and Vue Router.

Building a URL from a pattern

The reverse job fills a pattern with values, like React Router's generatePath("/users/:id", { id: "42" }). Each value must be encoded with encodeURIComponent, or a value with a / or space breaks the URL.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from :param, *, "which route matches", or "extract the values from the URL". The pieces are always separated by a fixed character, here /.
  • Explain the alignment first: since each piece matches exactly one segment, there's no searching, just a walk. Then mention the two ways to fail at the end: path too short (inside the loop) and path too long (after it).
  • Test by hand: a trailing slash, one extra segment, one missing segment, a wildcard with nothing after it, and an encoded character.
  • Expect the follow-up "what if * can appear in the middle, like /a/*/c?". Then the wildcard could match 1, 2, or more segments, so you have to try each length and back up when the rest fails, like matching a glob pattern.

Where frontend code uses it

The same idea in real UI code
  • React Router, Vue Router, and Next.js all match the current path against route patterns with :param or [param] segments and catch-all segments.
  • The URLPattern web API (new URLPattern({ pathname: "/users/:id" })) does this matching natively in browsers that support it.
  • Server frameworks like Express use the same pattern syntax, and service workers match request URLs to decide which caching strategy to use.

Related algorithms