Simplify Path medium

Problem Statement

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-like file system, convert it to the simplified canonical path.

In a Unix-like file system, a period '.' refers to the current directory, a double period '..' refers to the parent directory, and multiple slashes '/' are treated as a single slash. For instance, the path "/home//foo/" should be simplified to "/home/foo".

The path components are separated by '/'. Simplify the path by removing redundant '/'. If we encounter '..', we go up a level, so we need to pop from a stack or vector. If we encounter a '.', we do nothing. Otherwise, we append the component to a stack. Finally, we form the canonical path from the stack.

Example 1

Input: path = "/home//foo/" Output: "/home/foo" Explanation: Redundant slashes are removed, and there are no parent directory references.

Example 2

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

• "/a/./b/../../c/"
• After removing "." , we have "/a/b/../../c/"
• After removing ".." , we go up two levels:
  • From "/a/b/" to "/"
  • So we have "/c/"
• Then remove trailing slash. "/c"

Steps

1. Split the path: Split the input string path into its components using the '/' character as a delimiter. We will ignore empty components (resulting from multiple slashes).

2. Process components: Iterate through the components:

   • If a component is ".", ignore it.
   • If a component is "..", pop the last element from the stack (unless the stack is empty, indicating we're already at the root directory).
   • Otherwise (it's a regular directory name), push the component onto the stack.

3. Construct the canonical path: Join the elements in the stack with '/' and prepend a '/' if the stack is not empty. Remove any trailing '/'.

Explanation

The solution uses a stack (implemented as a vector in C++) to keep track of the directory path. The split function efficiently handles multiple slashes and empty components. The core logic iterates through the path components and applies the rules for ".", "..", and regular directory names. The final step constructs the canonical path from the stack contents.

Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> split(const std::string& str, char delimiter) {
    std::vector<std::string> result;
    std::string current;
    for (char c : str) {
        if (c == delimiter) {
            if (!current.empty()) {
                result.push_back(current);
                current = "";
            }
        } else {
            current += c;
        }
    }
    if (!current.empty()) {
        result.push_back(current);
    }
    return result;
}

std::string simplifyPath(std::string path) {
    std::vector<std::string> components = split(path, '/');
    std::vector<std::string> stack;
    for (const std::string& component : components) {
        if (component == "..") {
            if (!stack.empty()) {
                stack.pop_back();
            }
        } else if (component != ".") {
            stack.push_back(component);
        }
    }
    std::string result;
    for (const std::string& component : stack) {
        result += "/" + component;
    }
    if (result.empty()) {
        return "/";
    }
    return result.empty() ? "/" : result.substr(1); //remove leading slash if present
}

int main() {
    std::string path1 = "/home//foo/";
    std::string path2 = "/a/./b/../../c/";
    std::cout << simplifyPath(path1) << std::endl; // Output: /home/foo
    std::cout << simplifyPath(path2) << std::endl; // Output: /c
    return 0;
}

Complexity

• Time Complexity: O(N), where N is the length of the input string path. This is because we iterate through the string once to split it and then iterate through the components once to process them.

• Space Complexity: O(N) in the worst case, where N is the length of the input string. This is because the stack (vector) can potentially store all the components of the path. In the best case, the space complexity is O(1).