Simplify Path

Share

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 '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

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.
Constraints:

Contents

Solution 1 - Using a stack and read character by character from path

In this approach, we will read character by character and construct the path element, when we see '/' apply the rules such as if the current path element is .. then remove the path element before that, and if the path path element is . just skip it (since it is pointing to current directory). We will use a Stack datastructure to store the path elements, so that it makes it easy to apply these path rules, for example if the path is something like this /abc/def/ghi/../../.. simplified path will become / (root directory).

Implementation steps:
  • First, declare two variables stack, a Stack that we will use to store path elements, and current a Sting to store current path element.
  • Next, loop through each character of path string and if current character is / or if we reach of end of path do the following :
    • If the current value is .., and if the stack is not empty, then remove the top the element of stack and continue.
    • If the current value is not empty, and if it is NOT equal to ., then add the current path element into stack.
    • Reset the path to "" to empty, once we either do one of the above two steps.
  • If the current character is not /, then append the character to current string.
  • At the end, loop through stack elements, and create a new String with '/' separator.
Java
import java.util.Stack;

public class SimplifyPath {

    static String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String current = "";
        for(int i=0; i<=path.length(); i++) { // i<=path.length(), to handle what 'current' holds at the end loop
            if(i == path.length() || path.charAt(i) == '/') { //directory separator or end of path
                if("..".equals(current)) {
                    if(!stack.isEmpty()) stack.pop(); // is stack is not empty remove it , otherwise ignore it
                } else if (!current.isEmpty() && !".".equals(current)) {
                    stack.push(current);
                }
                current = "";
            } else {
                current += path.charAt(i);
            }
        }
        return "/" + String.join("/", stack);
    }

    public static void main(String[] args) {
        System.out.println(simplifyPath("/../abc//./def"));
        System.out.println(simplifyPath("/abc/def/ghi/../../.."));

    }
}
Complexity Analysis:

Time complexity: All the above operations runs in O(n) where n is the length of input string path.
Space complexity: O(n) for storing elements into stack.

Solution 2 - Using a stack and split the path string by '/'

In this approach, we will same approach as above, but instead of iterating through each character, we will use utility method String.split(regex) method using regular expression. '/'. (String's split() operation)

Java
import java.util.Stack;

public class SimplifyPath {

    static String simplyPathUsingStringSplit(String path) {
        Stack<String> stack = new Stack<>();
        String[] tokens = path.split("/");
        for(String token: tokens) {
            if("..".equals(token)) {
                if(!stack.isEmpty()) stack.pop();
            } else if (!token.isEmpty() && !".".equals(token) && !"/".equals(token)) {
                stack.push(token);
            }
        }

        return "/"+String.join("/", stack);
    }

    public static void main(String[] args) {
        System.out.println(simplyPathUsingStringSplit("/../abc//./def"));
        System.out.println(simplyPathUsingStringSplit("/abc/def/ghi/../../.."));

    }
}
Complexity Analysis:

Time complexity: All the above operations runs in O(n) where n is the length of input string path.
Space complexity: O(n) for storing elements into stack.

Above implementations source code can be found at GitHub link for Java code