71. Simplify Path

Intuition

The problem requires simplifying a Unix-style file path. Unix-style paths use "/" as a directory separator, "." to represent the current directory, and ".." to move up one directory. We need to handle these special symbols appropriately and ignore unnecessary slashes to create the canonical path. This can be effectively managed using a stack data structure to keep track of the directories.

Approach

1. Initialize a Stack: Use a stack to keep track of directory names.
2. Split the Path: Split the input path by the "/" delimiter to process each part individually.
3. Process Each Part: - Ignore empty parts and single periods ".". - For double periods "..", pop from the stack if it's not empty (this moves one directory up). - For any other directory name, push it onto the stack.
4. Build the Result Path: After processing all parts, join the elements in the stack with "/" to form the simplified path.
5. Edge Cases: Ensure the path starts with a single slash "/" and handle the root directory properly (the stack might be empty).

Complexity

Time Complexity:

O(n), where n is the length of the input path. Each character is processed once.

Space Complexity:

O(n), where n is the length of the input path. In the worst case, the stack could contain all directory names from the path.

Code

C++

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

Python

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

Java

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

JavaScript

var simplifyPath = function (path) {
    const stack = [];
    const directories = path.split("/");
    for (const dir of directories) 
    {
        if (dir === "." || !dir) 
        {
            continue;
        } else if (dir === "..") {
            if (stack.length > 0) {
                stack.pop();
            }
        } else {
            stack.push(dir);
        }
    }
    return "/" + stack.join("/");
};