Normalize a File Path

MediumStack

Problem

A backup tool receives absolute Unix-style paths such as /home//pablo/./docs/../notes/. Rewrite each path in canonical form.

Rules: . means the current directory and is dropped; .. moves up one directory (at the root it stays at the root); several consecutive slashes count as one; any other name, including ... or ..hidden, is an ordinary directory name.

The canonical path starts with a single /, separates names with single slashes, and has no trailing slash (except the root itself, /). Return it.

Example 1

Input:
path = "/home//pablo/./docs/../notes/"
Output:
"/home/pablo/notes"

The double slash collapses, . is dropped, and .. cancels docs.

Example 2

Input:
path = "/../"
Output:
"/"

Going up from the root stays at the root.

Constraints

  • 1 ≤ path.length ≤ 3000
  • path starts with '/'
  • path contains letters, digits, '.', '_' and '/'

Hint

Show the first hint

Split the path on '/' and look at the pieces one by one.

Walkthrough

How to approach it

01Clarify before coding

  • Is "..." special? No, only "." and ".." are; everything else is a name.
  • What does ".." at the root do? Nothing, you stay at "/".
  • Is the input always absolute? Yes, it always starts with '/'.

02Brute force

Repeatedly apply string rewrites (collapse "//", remove "/./", remove "/name/..") until the path stops changing.

Cost: Each rewrite pass is O(n) and there can be O(n) passes: O(n²), with many easy-to-miss special cases.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.