Leetcode 71. Simplify Path

Problem

Leetcode 71 - Simplify Path

Example:

Input: path = "/home/"
Output: "/home"
Explanation: The trailing slash should be removed.

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: Multiple consecutive slashes are replaced by a single one.

Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation: A double period ".." refers to the directory up a level (the parent directory).

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is not possible.

Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"
Explanation: "..." is a valid name for a directory in this problem.

Approach

As explained in the description of the problem,

• a single period ‘.’ represents the current directory
  • we can just ignore when we encounter ‘.’
• a double period ‘..’ represents the previous/parent directory
  • we can pop the stack if len(stack) > 0
• multiple consecutive slashes such as ‘//’ or ‘///’ are treated as single slash ‘/’
  • we can ignore this since .split(‘/’) will solve this
• any sequence of periods that does not match the rules above should be treated as a valid directory or file name.
  • append it to stack

When this is all done, we can join the stack with ‘/’. Since we must also start with ‘/’ for return value, we have to add ‘/’

Visualization of the Approach:

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

After doing split operation
path = ['', 'home', 'user', 'Documents', '..', 'Pictures']
stack = []

Since '' is empty, we ignore and continue
stack = []

Since 'home' is a valid name for directory add it to stack
stack = ['home']

Since 'user' is a valid name for directory add it to stack
stack = ['home', 'user']

Since 'Documents' is a valid name for directory add it to stack
stack = ['home', 'user', 'Documents']

Since '..', we should pop one from stack if len(stack) > 0
stack = ['home', 'user']

Since 'Pictures' is a valid name for directory add it to stack
stack = ['home', 'user', 'Pictures']

When we return we must add '/' first then join the list with '/'
Thus, res = '/home/user/Pictures'

Here is the Python code for the solution:

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        path = path.split('/')

        for p in path:
            if p == '':
                continue
            elif p == '.':
                continue
            elif p == '..':
                if len(stack) == 0:
                    continue
                else:
                    stack.pop()
            else:
                stack.append(p)
        
        return '/' + '/'.join(stack)

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$