Leetcode 71: Simplify Path

1. Problem Statement (Simple Explanation)

You’re given an absolute Unix-style path string path that:

• Always starts with '/'.

• May contain:

• directory names (letters, digits, _, more periods, etc.)

• special entries:

• "." → current directory (ignore it)

• ".." → parent directory (go up one level if possible)

• multiple slashes "//", "///", which are treated as a single slash.

You must return the simplified canonical path, such that:

• Starts with exactly one '/'.

• Directories are separated by a single '/'.

• No trailing slash (unless the path is just root /).

• No "." or ".." segments remain.

• "...", "...." etc. are treated as normal directory names.

2. Examples

Example 1:

Input: path = "/home/"

Output: "/home"

Trailing slash removed.

Example 2:

Input: path = "/home//foo/"

Output: "/home/foo"

Multiple slashes collapsed; trailing slash removed.

Example 3:

Input: path = "/home/user/Documents/../Pictures"

• Documents/.. → go up from Documents to user.

Output: "/home/user/Pictures"

Example 4:

Input: path = "/../"

You cannot go above root; stay at root.

Output: "/"

Example 5:

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

• "..." is a normal directory name.

• Steps:

• /.../ → ["..."]

• a → ["...", "a"]

• .. → pop "a" → ["..."]

• b → ["...", "b"]

• c → ["...", "b", "c"]

• .. → pop "c" → ["...", "b"]

• d → ["...", "b", "d"]

• . → ignore

Output: "/.../b/d"

3. Approach – Split + Stack (O(n))

We can treat path segments between '/' as tokens:

1. Split path on '/'.

2. For each token:

• If token is empty ("") or ".":

• Ignore it.

• Else if token is "..":

• Pop last directory from stack if stack is not empty.

• Else:

• It’s a normal directory name (including "...", "....", etc.); push onto stack.

3. After processing all tokens:

• If stack is empty → canonical path is "/".

• Else:

• Join stack with '/' and prefix with '/'

• "/" + "/".join(stack)

This naturally handles multiple slashes ("" tokens) and special segments.

Pseudo-code:

Complexity:

Let n = len(path):

• Splitting and scanning: O(n)

• Stack operations: O(n) (each segment pushed/popped at most once).

• Overall time: O(n), space: O(n) for tokens/stack and result.

4. Java code

5. C code

Note: The C version modifies path in-place due to strtok, so in strict environments you should first strdup() the input string.

6. C++ code

7. Python code

8. JavaScript code