71.Simplify_Path(Medium).md

71. Simplify Path (Medium)

Date and Time: Nov 17, 2024, 11:36 (EST)

Link: https://leetcode.com/problems/simplify-path/

Question:

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

• A single period '.' represents the current directory.

• A double period '..' represents the previous/parent directory.

• Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.

• Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

• The path must start with a single slash '/'.

• Directories within the path must be separated by exactly one slash '/'.

• The path must not end with a slash '/', unless it is the root directory.

• The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

Example 1:

Input: path = "/home/"

Output: "/home"

Explanation:
The trailing slash should be removed.

Example 2:

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

Output: "/home/foo"

Explanation:
Multiple consecutive slashes are replaced by a single one.

Example 3:

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

Output: "/home/user/Pictures"

Explanation:
A double period ".." refers to the directory up a level (the parent directory).

Example 4:

Input: path = "/../"

Output: "/"

Explanation:
Going one level up from the root directory is not possible.

Example 5:

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

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

Explanation:
"..." is a valid name for a directory in this problem.

Constraints:

• 1 <= path.length <= 3000

• path consists of English letters, digits, period '.', slash '/' or '_'.

• path is a valid absolute Unix path.

Walk-through:

1. Loop over path and for each char c in path, we only need to check if c == '/' or not.

2. If c == '/', when tmp is not empty, and tmp != '.', we can append the current tmp into stack[]. So, it will avoid the multiple consecutive slashes '//'.
   Also, we check tmp != '.' so we don't add single dot into stack[], and we want to reset tmp to empty string.

3. For other cases, we just add c to tmp.

4. Lastly, join every path_name/directory into a string with delimiter '/' and we add a single slash in the beginning.

We looping over path + '/' to avoid cases like Example 3, so we can successfully add the last file name without slash into stack, also the algorithm will handle multiple consecutive slashes.

Note: we have to check if stack: separately, if not, when stack is empty, the elif condition will be True, so we will add '..' into stack.

Python Solution:

class Solution:
    def simplifyPath(self, path: str) -> str:
        # If c == '/': 
        # i. if tmp != "", we can stop adding char into tmp
        # ii. this is the first slash in tmp, don't do anything
        # iii. check if cur == '..'
        # Other cases we can just add cur += c and until we meet another '/', we append the word to stack
        # Lastly, join every char with delimiter "/"
        
        # TC: O(n), n = len(path), SC: O(n)
        stack = []
        tmp = ""
        for c in path + '/':
            if c == '/':
                if tmp == "..":
                    # Otherwise, '..' will be added to stack, which is wrong
                    if stack:
                        stack.pop()
                # when it's not the first slash
                elif tmp != "" and tmp != ".":
                    stack.append(tmp)
                # If there is single dot or other slashes, reset tmp
                tmp = ""
            else:
                tmp += c
        # Join every name from stack into string with '/'
        return "/" + "/".join(stack)

Time Complexity: $O(n)$
Space Complexity: $O(n)$