beta

Practice problem · easy

Longest common prefix of route paths

Engineering platformpractice problem 3 of the lessonup to 18 Bits0/5 hints open

Scenario

A web server routes each address by its start. To group the routes under one handler, the team needs the longest start that every route path shares.

You get the list of route paths, such as /shop/men/shirts. You must return the longest prefix that all of them have in common.

Your task

Write common_prefix(paths).

paths are the route paths, made of lowercase letters and /. The same path can appear more than once.
Return the longest string that is a prefix of every path.
Return an empty string when the paths share no start at all. The prefix may end in the middle of a name.

Examples

Example 1 (traced)#

text2 lines

Input:  paths = ["/shop/men/shirts", "/shop/men/shoes", "/shop/women"]
Output: "/shop/"

| Node reached | Next characters in the list | What happens |\n|---|---|---|\n| /shop | / only | go on |\n| /shop/ | m and w | two ways: stop |\n\nAll three paths start with /shop/, and then they split.

Example 2#

text2 lines

Input:  paths = ["/a", "/b"]
Output: "/"

Both paths start with /, and then a and b differ.

Example 3#

text2 lines

Input:  paths = ["/home"]
Output: "/home"

With one path, the whole path is the longest shared start.

Constraints

1 ≤ length of paths ≤ 2000
Every path has 1 to 100 characters, each one a lowercase letter (a to z) or /

What does the size limit tell you?

There can be 2,000 paths of 100 characters, so 200,000 characters in all. Reading each character once is fast.

A trie fits well: the shared start is the path from the root where each node has only one way to go.

write common_prefix · runs in your browser

Loading the editor…

Run tries the examples · Submit checks every test

Coding is easiest on a laptop. On a phone, read, trace and try small edits.

Practice problem · easy

Longest common prefix of route paths

Lesson: Tries~15 min

Engineering platformpractice problem 3 of the lessonup to 18 Bits0/5 hints open

Scenario

A web server routes each address by its start. To group the routes under one handler, the team needs the longest start that every route path shares.

You get the list of route paths, such as /shop/men/shirts. You must return the longest prefix that all of them have in common.

Your task

Write common_prefix(paths).

paths are the route paths, made of lowercase letters and /. The same path can appear more than once.
Return the longest string that is a prefix of every path.
Return an empty string when the paths share no start at all. The prefix may end in the middle of a name.

Examples

Example 1 (traced)#

text2 lines

Input:  paths = ["/shop/men/shirts", "/shop/men/shoes", "/shop/women"]
Output: "/shop/"

Example 2#

text2 lines

Input:  paths = ["/a", "/b"]
Output: "/"

Both paths start with /, and then a and b differ.

Example 3#

text2 lines

Input:  paths = ["/home"]
Output: "/home"

With one path, the whole path is the longest shared start.

Constraints

1 ≤ length of paths ≤ 2000
Every path has 1 to 100 characters, each one a lowercase letter (a to z) or /

What does the size limit tell you?

There can be 2,000 paths of 100 characters, so 200,000 characters in all. Reading each character once is fast.

A trie fits well: the shared start is the path from the root where each node has only one way to go.

write common_prefix · runs in your browser

Loading the editor…

Run tries the examples · Submit checks every test

Coding is easiest on a laptop. On a phone, read, trace and try small edits.