By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 71. Simplify Path.

Intuition

We can just simulate the process from the begin to end.

First we split the given string \(\textit{path}\) into a list of strings by the slash \(/\), denoted as names. According to the canonical path in the problem description, the strings contained in names can only be the following:

1. empty string;
2. a dot .;
3. two dots ..;
4. a directory name containing only English letters, numbers, or _.

If we meet empty string or ., we can ignore them because empty string means nothing, and . means the current directory itself, so we don’t need to change directories.

If we meet .. or “directory names”, we can use a Stack to maintain each directory name in the path. When we encounter “two dots”, we need to change the directory to the parent directory. As the stack is not empty, we pop the directory of the stack. When we encounter a “directory”, we put it to the stack.

Finally we need to iterate each string in names and do the above. After all operations are completed, we connect the strings from the bottom of the stack to the top of the stack with /, and then add / at the top to indicate the root directory, and we can get the simplified Canonical path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public String simplifyPath(String path) {
        if (path == null || path.length() <= 1) {
            return "/";
        }

        Stack<String> pathStack = new Stack<>();
        StringBuilder ans = new StringBuilder();
        path = path.replaceAll("\\/\\/", "/");
        String[] folders = path.split("\\/");
        int len = folders.length;
        for (int i = 0; i < len; i++) {
            String folder = folders[i];
            if (folder.equalsIgnoreCase(".")) {
                continue;
            } else if (folder.equalsIgnoreCase("..")) {
                if (!pathStack.empty()) {
                    pathStack.pop();
                }
            } else if (folder.length() > 0) {
                pathStack.push(folder);
            }
        }

        ans.append('/');
        List<String> res = new ArrayList<>();
        while (!pathStack.empty()) {
            res.add(pathStack.pop());
        }

        for (int i = res.size() - 1; i >= 0; i--) {
            ans.append(res.get(i));
            ans.append("/");
        }

        if (ans.length() > 1 && ans.charAt(ans.length() - 1) == '/') {
            ans.deleteCharAt(ans.length() - 1);
        }

        return ans.toString();
    }
}

1
2
3
4
5
6
7
8
9

class Solution:
    def simplifyPath(self, path: str) -> str:
        ans = []
        for p in path.split("/"):
            if p == ".." and ans:
                ans.pop()
            elif p not in "..":
                ans.append(p)
        return "/" + "/".join(ans)

1
2
3
4
5
6
7
8
9
10
11

func simplifyPath(path string) string {
    ans := []string{}
    for _, s := range strings.Split(path, "/") {
        if s != "" && s != "." && s != ".."{
            ans = append(ans, s)
        } else if s == ".." && len(ans) > 0{
            ans = ans[:len(ans) - 1]
        }
    }
    return "/" + strings.Join(ans, "/")
}

Analysis

• Time Complexity: \(O(N)\).
• Space Complexity: \(O(N)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗