Simplify Path

Medium#71one step back

You get an absolute Unix-style path. Write it the shortest way: one "/" between folders, none at the end, no "." (the current folder) and no ".." (the folder above, which at the root stays at the root). Our example: "/../srv//www/./tmp/../app/" becomes "/srv/www/app".

71 Simplify PathWalkthrough · 1×

Example: "/../srv//www/./tmp/../app/", split on "/" into 10 parts; "" is an empty part. Below them is the stack of folders we are in, the newest on the right.

0""1..2srv3""4www5.6tmp7..8app9""folders—
not read yetpart, read now; a folder just pushedread, nothing to keepa folder on the stackpopped by ".."in the answer

Start at the root: no folders on the stack

01/25
restart · back · play · step
Speed
1function simplifyPath(path):
2 folders = empty stack
3 for each part in split(path, "/"):
4 if part is "" or part is ".":
5 continue
6 if part is "..":
7 if folders is not empty:
8 pop from folders
9 else:
10 push part onto folders
11 return "/" + join(folders, "/")
state
path
"/../srv//www/./tmp/../app/"
folders
[]
part
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The stack is the path so far: the folders from the root down to where we stand. Going into a folder pushes it, and ".." leaves the folder entered last, which is the top.
  2. Empty parts and "." do not move us, so they are skipped. ".." at the root has nothing to pop and is skipped too: above the root is still the root.
  3. Only folder names reach the stack, so joining it with "/" gives the shortest path, with no doubled slash and none at the end.

Complexity

Time O(n) for a path of n characters: the split and the join each read it once, and each part is pushed or popped at most once. Memory O(n) for the parts and the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.