Leetcode 71. Simplify Path

Explanation

Given an absolute path for a file (Unix-style), the task is to simplify it, or convert it to a canonical format. A canonical path is the simplest and shortest path that can represent a specific file or folder. It starts with a slash (/) and has only one slash between two directory names.

In an UNIX-style file system, a period (.) refers to the current directory, while a double period (..) moves the directory up by one level. Our task is to convert the provided path into canonical form considering these rules.

For example, if the input is "/../", the output should be "/". This is because ".." signifies moving up one directory level from the current directory. Since we are at the root level (indicated by "/"), we can't move up any further, so the canonical path remains "/".

Another example is "/home//foo/". Here, the canonical path is "/home/foo". This is because consecutive slashes are replaced by a single one in a canonical path.

The solution for this problem can be implemented using Stack data structure and String operations. We iterate over the directories in the path and handle three conditions:

  1. If the directory is "." or empty, we ignore it and move to the next directory
  2. If the directory is "..", we pop the last directory from our stack to signify moving up one directory level.
  3. If the directory is not "." or "..", we push it into our stack.

At the end, we construct our canonical path using the directories in our stack. Each remaining directory is appended to the canonical path with a "/" before it.

Python Solution

1
2python
3class Solution:
4    def simplifyPath(self, path: str) -> str:
5        stack = []
6        dirs = path.split("/")
7        for dir in dirs:
8            if dir == "..":
9                if stack: 
10                    stack.pop()
11            elif dir and dir != ".":
12                stack.append(dir)
13        return "/" + "/".join(stack)

Java Solution

1
2java
3class Solution {
4    public String simplifyPath(String path) {
5        Deque<String> stack = new LinkedList<>();
6        for(String s: path.split("/")) {
7            if(s.equals("..")) {
8                if(!stack.isEmpty()) 
9                    stack.pop();
10            } else if(!s.isEmpty() && !s.equals("."))
11                stack.push(s);
12        }
13        String res = "";
14        for(String s: stack) 
15            res = "/" + s + res;
16        return res.isEmpty() ? "/" : res;
17    }
18}

Javascript Solution

1
2javascript
3class Solution {
4    simplifyPath(path) {
5        let stack = [];
6        let dirs = path.split('/');
7        for(let dir of dirs) {
8            if(dir === "..") {
9                if(stack.length) 
10                    stack.pop();
11            } else if(dir && dir !== ".")
12                stack.push(dir);
13        }
14        return "/" + stack.join('/');
15    }
16}

C++ Solution

1
2cpp
3class Solution {
4public:
5    string simplifyPath(string path) {
6        vector<string> stack;
7        stringstream ss(path);
8        string dir;
9        while(getline(ss, dir, '/')) {
10            if(dir == "" || dir == ".") 
11                continue;
12            if(dir == ".." && !stack.empty()) 
13                stack.pop_back();
14            else if(dir != "..") 
15                stack.push_back(dir);
16        }
17        string res = "";
18        for(auto& str : stack)
19            res += "/" + str;
20        return res.empty() ? "/" : res;
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public string SimplifyPath(string path) {
5        var stack = new Stack<string>();
6        var dirs = path.Split('/');
7        foreach(var dir in dirs) {
8            if (dir == "..") {
9                if (stack.Any()) 
10                    stack.Pop();
11            } else if(!string.IsNullOrEmpty(dir) && dir != ".")
12                stack.Push(dir);
13        }
14        var res = string.Join("/", stack.Reverse());
15        return "/" + res;
16    }
17}

These solutions all make use of a few common principles. They all approach the problem by iterating over the directories in the path and applying the specified rules. This is done by using a stack to keep track of the current canonical path. If the directory is '.' or empty (because of consecutive slashes), it is ignored. If the directory is '..', the last directory is popped from the stack, signifying moving up by one directory level. Any other kind of directory is simply pushed into the stack.

After iterating over all the directories, the canonical path is constructed by joining all the directories in the stack, separated by a single '/'. This guarantees an absolute path, containing only one slash between directories. Even if there are no directories left in the stack (for example when the path was '/../'), the leading slash in the output will ensure that the result is an absolute path pointing to the root directory.

All proposed solutions use the built-in functionality of various programming languages to solve the task. They all share similar time and space complexity because they perform the same operations and hold the same amount of data. This solution has a time complexity of O(n), where n is the number of characters in the input path. This is because we perform a constant amount of work (a few comparisons and possibly a stack operation) for each character in the input. The space complexity is also O(n), because in the worst-case scenario, we have to store all directories of the input path in the stack.

Altogether, these solutions offer a clear, effective way to simplify a given file path. Test them with different file paths to see their effectiveness. Remember that the shortest and simplest path to a file may not always be the most effective path so always make sure to test solutions on various test cases to ensure correctness.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫