medium

Simplify Path

Turn a Unix file path into its canonical form by pushing folder names and popping one off for every ".." part.

1. Define the problem

Simplify Path

You are given a file path written in Unix style, and you must return its canonical form — the shortest path that points at the same place. The path is split by slashes into parts. A part that is "." means "stay where you are". A part that is ".." means "go up one folder". Empty parts come from repeated slashes and mean nothing at all. Anything else is a folder name. A stack of folder names models this exactly: entering a folder pushes its name, and ".." pops the last folder back off. Going up from the root does nothing, which a pop on an empty stack already handles. The answer always starts with a single slash and never ends with one, unless it is just the root .

Constraints

  • 1 ≤ path.length ≤ 3000
  • The path always starts with a single slash
  • Folder names contain letters, digits, dots and underscores
  • The path may contain repeated slashes, "." and ".."
  • Going up from the root leaves you at the root

Example

Inputpath = "/a/./b/../c/"
Output"/a/c"

Explanation Enter a, stay put for ".", enter b, then ".." leaves b, then enter c. The folders you are standing in are a and c.

2. Know the words first

In plain terms

Path
The address of a file or folder, written as folder names separated by slashes, for example /home/photos.
Root
The very top of the file system, written as a single slash.
Canonical form
The one tidy way of writing a path: one slash between names, no "." or ".." left, and no trailing slash.
Stack
A pile where you add and remove only at the top. Here the top is the folder you are currently standing in.
3. Visualize the solution

The row is the stack of folders you are standing in, root on the left

The row is the stack of folders you are standing in, root on the left
Statusinit

Start at the root with an empty stack of folders.

What happens in this step

path = "/a/./b/../c/"
parts = ["", "a", ".", "b", "..", "c", ""]
stack = []

An empty stack means you are standing at the root.
Step 1 of 7

Steps to visualize

  1. Each filled cell is one folder name. A dash means an empty slot, and an empty stack means the root.
  2. Split the path on slashes and read the parts one at a time.
  3. An empty part or "." changes nothing at all.
  4. A part of ".." pops the top folder off, which is exactly going up one level.
  5. Any other part is a folder name and gets pushed on top.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of folders you are standing in, root on the left
Statusinit

Start at the root with an empty stack of folders.

What happens in this step

path = "/a/./b/../c/"
parts = ["", "a", ".", "b", "..", "c", ""]
stack = []

An empty stack means you are standing at the root.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function simplifyPath(path) {
  const stack = [];
  const parts = path.split('/');

  for (const part of parts) {
    if (part === '' || part === '.') {
      continue;
    }

    if (part === '..') {
      stack.pop();
    } else {
      stack.push(part);
    }
  }

  return '/' + stack.join('/');
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
path = "/a/./b/../c/""/a/c"example from the description, using ".", ".." and a trailing slash
path = "/home/""/home"the trailing slash is dropped
path = "/home//foo/""/home/foo"repeated slashes make empty parts that mean nothing
path = "/../""/"going up from the root leaves you at the root
path = "/""/"smallest possible path
path = "/a/b/c/../../d/""/a/d"two levels up in a row, then a new folder

Keep reading