Detailed explanation of the simplified path example of Go Java algorithm

Simplify the path

Give you a string path that represents a Unix-style absolute path (starting with '/') to a file or directory, please convert it into a more concise and standard path.

In a Unix-style file system, a point (.) represents the current directory itself; in addition, two points (..) represent switching the directory to the previous level (pointing to the parent directory); both can be part of complex relative paths.

Any multiple consecutive slashes (i.e., '//') are treated as single slashes '/' . For this problem, any other format dots (e.g., '...') are treated as file/directory names.

Note that the returned canonical path must follow the following format:

Always start with a slash '/'.

There must be only one slash between the two directory names '/' .

The last directory name (if present) cannot end with '/'.

Additionally, the path contains only directories on the path from the root directory to the target file or directory (i.e., without '.' or '..').

Returns the simplified canonical path.

• Example 1:

Enter: path = "/home/"

Output: "/home"

Explanation: Note that there is no slash after the last directory name.

• Example 2:

Enter: path = "/../"

Output: "/"

Explanation: It is not feasible to go from the root to the next level, because the root directory is the highest level you can reach.

• Example 3:

Enter: path = "/home//foo/"

Output: "/home/foo"

Explanation: In the canonical path, multiple continuous slashes need to be replaced with one slash.

• Example 4:

Enter: path = "/a/./b/../../c/"

Output: "/c"

hint:

1 <= <= 3000

path consists of English letters, numbers, '.', '/' or '_'.

path is a valid Unix style absolute path.

Method 1: Stack (Java)

We first divide the given string path into a list of several strings according to / and record it as names.

For "empty strings" and "a dot", we don't actually need to process them, because "empty strings" have no meaning, while "a dot" means the current directory itself, and we don't need to switch directories.

For "two points" or "directory name", we can use a stack to maintain each directory name in the path. When we encounter "two points", we need to switch the directory to the previous level, so as long as the stack is not empty, we will pop up the directory at the top of the stack. When we encounter a "directory name", we put it on the stack.

class Solution {
    public String simplifyPath(String path) {
        String[] names = ("/");
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!()) {
                    ();
                }
            } else if (() > 0 && !".".equals(name)) {
                (name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (()) {
            ('/');
        } else {
            while (!()) {
                ('/');
                (());
            }
        }
        return ();
    }
}

Time complexity: O(N)

Space complexity: O(N)

Method 2: Standard Library (Go)

For specific methods and ideas, please refer to the statement above. Since Go's own standard library already has this capability, it can be done by simply calling the standard library.

import (
	path2 "path"
)
func simplifyPath(path string) string {
	return (path)
}

Time complexity: O(N)

Space complexity: O(N)

The above is the detailed explanation of the simplified path example of Go Java algorithm. For more information about simplified paths of Go Java algorithm, please pay attention to my other related articles!