Code Implementation

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part == '' or part == '.':
                continue
            elif part == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(part)
        return '/' + '/'.join(stack)
      

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        stringstream ss(path);
        string part;
        while (getline(ss, part, '/')) {
            if (part == "" || part == ".") continue;
            if (part == "..") {
                if (!stack.empty()) stack.pop_back();
            } else {
                stack.push_back(part);
            }
        }
        string result = "/";
        for (int i = 0; i < stack.size(); ++i) {
            result += stack[i];
            if (i != stack.size() - 1) result += "/";
        }
        return result;
    }
};
      

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        String[] parts = path.split("/");
        for (String part : parts) {
            if (part.equals("") || part.equals(".")) continue;
            if (part.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else {
                stack.push(part);
            }
        }
        StringBuilder result = new StringBuilder();
        for (String dir : stack.descendingIterator()) {
            result.append("/").append(dir);
        }
        return result.length() == 0 ? "/" : result.toString();
    }
}
      

var simplifyPath = function(path) {
    const stack = [];
    const parts = path.split('/');
    for (let part of parts) {
        if (part === '' || part === '.') continue;
        if (part === '..') {
            if (stack.length) stack.pop();
        } else {
            stack.push(part);
        }
    }
    return '/' + stack.join('/');
};
      

Problem Description

Given a string path representing an absolute path for a file or directory in a Unix-style file system, simplify it and return the canonical path.

The canonical path must:

• Start with a single slash /.
• Have only one slash between directory names (no consecutive slashes).
• Ignore . (current directory) and resolve .. (move up one directory).
• Not end with a trailing slash (unless it is the root /).

The problem guarantees there is exactly one valid simplified path for any input.

Thought Process

At first glance, the problem seems to require parsing and cleaning up a string. However, the challenge lies in correctly handling the special tokens . and .., as well as redundant slashes. A brute-force approach might involve repeatedly searching for these patterns and replacing them, but this quickly becomes complex and error-prone.

Instead, it's helpful to think of the path as a sequence of directory entries that can be processed one by one, similar to how a stack works. Every time we see a normal directory name, we move deeper (push onto stack). When we see .., we move up (pop from stack). . and empty strings (from double slashes) are simply ignored. This stack-based approach is both intuitive and efficient, avoiding unnecessary string manipulation.

Solution Approach

• Split the Path: Begin by splitting the input string path by the slash / character. This gives a list of directory names and special tokens (., .., or empty strings).
• Use a Stack: Initialize an empty stack to keep track of the valid directory names as we process each part.
• Process Each Part:
  • If the part is empty ("") or a single dot ("."), do nothing (ignore).
  • If the part is "..", pop from the stack if it is not empty (move up one directory).
  • Otherwise, the part is a valid directory name; push it onto the stack.
• Reconstruct the Path: Join the stack with '/' to form the simplified path. Always start with a single /. If the stack is empty, the result is just "/".

This method efficiently handles all the requirements using a single pass through the path, and the stack ensures that .. always removes the most recently added directory.

Example Walkthrough

Let's consider the input: "/a/./b/../../c/"

1. Split into parts: ["", "a", ".", "b", "..", "..", "c", ""]
2. Process each part:
   • "": ignore
   • "a": push to stack → ["a"]
   • ".": ignore
   • "b": push to stack → ["a", "b"]
   • "..": pop → ["a"]
   • "..": pop → []
   • "c": push → ["c"]
   • "": ignore
3. Join stack: "/c"

The canonical path is "/c".

Time and Space Complexity

• Brute-force Approach: If you tried to repeatedly replace /./ and /../ patterns in the string, you could end up with O(N^2) time due to repeated scanning and string rebuilding.
• Optimized Stack Approach:
  • Time Complexity: O(N), where N is the length of the input string. We process each character once to split and each part once to process.
  • Space Complexity: O(N), for the stack and the split parts.

Summary

The key to simplifying a Unix-style path is to process each segment in order, using a stack to handle directory traversal. This approach elegantly handles all edge cases—redundant slashes, . for current directory, and .. for moving up. By focusing on stack operations, we achieve a clean, efficient, and easily understandable solution that runs in linear time.