Simplify Path medium

Problem Statement

Given a string representing a file system path, simplify it. A simplified path consists of only the directories, while removing dots (.), double dots (..), and redundant slashes (//).

Example 1

Input: "/home//foo/" Output: "/home/foo" Explanation: The redundant slashes are removed.

Example 2

Input: "/a/./b/../../c/" Output: "/c" Explanation:

1. "/a/./b/../../c/" -> "/a/b/../../c/" (. is removed)
2. "/a/b/../../c/" -> "/a/../../c/" (double dot goes up one level)
3. "/a/../../c/" -> "/c" (double dot goes up two levels; when the current level is the root, it remains root)

Steps

1. Split the path: Split the input string into individual path components using the / character as a delimiter.
2. Process each component: Iterate through the components and handle each case:
   • If the component is empty or ".", ignore it.
   • If the component is "..", pop the last element from the stack (if it's not empty).
   • Otherwise, push the component onto the stack.
3. Construct the simplified path: After processing all components, join the elements in the stack using / as a separator. Add a leading / if the stack is not empty.

Explanation

The solution uses a stack to efficiently manage the path components. The stack's LIFO (Last-In, First-Out) nature perfectly mirrors the hierarchical structure of a file system. When encountering "..", we go up one level by removing the previously added directory from the stack. The use of a stack avoids the need for complex string manipulation and makes the logic more clear and concise.

Code

import java.util.Stack;

class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] components = path.split("/");

        for (String component : components) {
            if (component.equals("") || component.equals(".")) {
                continue; // Ignore empty strings and "."
            } else if (component.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop(); // Go up one level
                }
            } else {
                stack.push(component); // Add the component to the stack
            }
        }

        StringBuilder simplifiedPath = new StringBuilder();
        if (stack.isEmpty()) {
            return "/"; // Handle the case where the path is empty after simplification.
        } else {
          while(!stack.isEmpty()){
              simplifiedPath.insert(0, stack.pop());
              simplifiedPath.insert(0, "/");
          }
          return simplifiedPath.toString().substring(1); //Removes the initial redundant "/"
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the input string. We iterate through the string components once.
• Space Complexity: O(N) in the worst case. The stack can potentially store all the path components if there are no ".." to remove. In the best case (e.g., "/a/b/c"), the space complexity is O(1).