Simplify Path

Medium · stack

You are given path, a file system path written as a string. It always starts with /, and its parts are separated by slashes. Each part means one of these:

A name such as home or notes_2 means "step into that directory". Names can contain dots too: ... and .hidden are ordinary names.
. means "stay where you are".
.. means "go up to the parent directory". Going up from the root / leaves you in the root.

Several slashes in a row count as a single slash.

Return the shortest path that ends up in the same place. It must start with a single /, join the directory names with single slashes, have no slash at the end (unless the answer is the root itself, which is /), and contain no . or .. parts.

Examples

Example 1

Input: path = "/home//user/./docs/"

Output: "/home/user/docs"

The double slash counts as one, the . changes nothing and the trailing slash is dropped.

Example 2

Input: path = "/a/b/../../../c"

Output: "/c"

Two .. climb out of a and b. The third tries to go above the root and stays there, then c is entered.

Example 3

Input: path = "/.../x/"

Output: "/.../x"

... is an ordinary name, so it is kept.

Constraints

1 <= len(path) <= 3000
path consists of letters, digits, ., _ and /.
path starts with /.