algoadvance

Leetcode 71. Simplify Path

Problem Statement

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

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e., ‘//’) are treated as a single slash ‘/’. The canonical path should have the following format:

Return the simplified canonical path.

Example 1:

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Clarifying Questions

  1. Are there any other special characters I need to handle apart from ‘.’ and ‘..’?
    • No, apart from ‘.’ and ‘..’, you only have regular directory names and slashes to handle.
  2. Should I handle invalid paths?
    • No, you can assume the input path is always valid.
  3. Are all inputs starting with ‘/’?
    • Yes, all inputs are absolute paths starting with ‘/’.

Strategy

  1. Split the input path by the delimiter ‘/’.
  2. Use a stack to keep track of directory names.
  3. Iterate through each part of the split path:
    • If the part is ‘..’, pop from the stack if it is not empty.
    • If the part is ‘.’ or empty, continue to the next part.
    • Otherwise, push the directory name onto the stack.
  4. Construct the canonical path by joining the directory names in the stack with ‘/’.
  5. Return “/” if the stack is empty; otherwise, return the constructed path.

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>

std::string simplifyPath(std::string path) {
    std::stack<std::string> st;
    std::istringstream ss(path);
    std::string token;

    while (std::getline(ss, token, '/')) {
        if (token == "..") {
            if (!st.empty()) {
                st.pop();
            }
        } else if (!token.empty() && token != ".") {
            st.push(token);
        }
    }

    std::string simplifiedPath;
    while (!st.empty()) {
        simplifiedPath = "/" + st.top() + simplifiedPath;
        st.pop();
    }

    return simplifiedPath.empty() ? "/" : simplifiedPath;
}

int main() {
    // Test cases
    std::vector<std::string> testCases = {"/home/", "/../", "/home//foo/"};
    for (const auto &path : testCases) {
        std::cout << "Input: " << path << "\nOutput: " << simplifyPath(path) << "\n\n";
    }
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string. This is because we process each character in the path string exactly once.

The space complexity is O(n) as well, for storing the split parts and for the stack, both of which in the worst case can contain all the directory names in the path.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI