~/problems / Stacks / Stack: path parsing

Simplify Path

easy ~15 min

Write simplify_path(path) -> str that turns an absolute Unix-style path into its canonical form.

Rules for the input:

  • It always starts with /.
  • Runs of slashes (//, ///) act like a single /.
  • . means "this directory" and is dropped.
  • .. means "go up one directory"; going up from the root stays at the root.
  • Any other name, including ones made of dots like ... or ..a, is an ordinary directory name.

The canonical form starts with a single /, separates names with single slashes, has no trailing slash (unless it is just /), and contains no . or .. entries.

simplify_path("/usr//local/./bin/")      # "/usr/local/bin"
simplify_path("/a/b/../../../c")         # "/c"
simplify_path("/../")                    # "/"
simplify_path("/x/.../y/..")             # "/x/..."

Constraints:

  • 1 <= len(path) <= 3000; path holds only letters, digits, ., _ and /.
  • Aim for O(len(path)).
Show hint

split on / and keep the directory names on a stack.

Topic: Stack: path parsing. Resolve ., .. and symlinks with a stack.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc