“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The simplified path of question 71 is as follows:

Given a string path representing a Unix-style absolute path (beginning with a ‘/’) to a file or directory, convert it to a more concise canonical path.

In Unix-style file systems, a dot (.) Represents the current directory itself; In addition, two points (..) Indicates that the directory is switched to a higher level (pointing to the parent directory). Both can be part of a complex relative path. Any number of consecutive slashes (that is, ‘//’) are treated as a single slash ‘/’. For this problem, any other format of the point (for example, ‘… ‘) are treated as file/directory names.

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

  • Always with a slash'/'At the beginning.
  • There must be only one slash between the two directory names'/' 。
  • Last directory name (if present)Can’t 以 '/'At the end.
  • In addition, the path contains only directories on the path from the root directory to the target file or directory (that is, none'. ' 或 '.. ').

Returns the simplified canonical path.

Example 1:

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

Example 2:

Enter: path = "/a/./b/.. /.. /c/" output:Copy the code

A, thinking

When I started working on this problem, I was going to use the re to replace certain things in the string. Later found unable to handle.. and.. Logic problems.

Later I found that the simplified path is to find the names of all files, not including. And.. Is to go back to the parent directory, we can use the stack to implement this logic.

The general steps are as follows:

  1. Based on the/Group strings, such as string arraysarrYou don’t have any/ 了
  2. traversearr, there are three situations
    • Empty strings and.: Do not perform any operation at this time
    • string.: Pushes the stack back to the previous directory
    • All other cases are pushed
  3. Iterate through the stack to spell out the complete path.

Tips: Why do empty strings appear after using/grouping? A: Null characters are always present in cases like ‘/’ or paths with ‘//’ in them

For example

Here is the example “/a/./b/.. /.. /c/” as an example

  1. through/The result after grouping isarr = {"", "a", ".", "b", ".." , ".." , "c"}
  2. To traverse thearrwheni=0When,arr[0] 为 "", discard it
  3. wheni=1When,arr[1] = "a", into the stack. Stack for"a"
  4. wheni=2When,arr[2] = "."And discarded.
  5. wheni=3When,arr[3] = "b", into the stack. Stack for"a" -> "b"
  6. wheni=4When,arr[4] = "..", stack top out stack. Stack for"a"
  7. wheni=5When,arr[5] = "..", stack top out stack. Stack for ` `
  8. wheni=6When,arr[6] = "c", into the stack. Stack for"c"
  9. Returns the result"/c"Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public String simplifyPath(String path) {
        // Use slashes to split strings
        String[] arr = path.split("/");
        Stack<String> stack = new Stack<>();
        for (String str : arr) {
            if ((".").equals(str) || ("").equals(str)) {    // Current directory
                // Do nothing
            } else if ("..".equals(str)) {  // One step up
                if(! stack.isEmpty()) {// The stack is not emptystack.pop(); }}else{ stack.push(str); }}// Iterate through the stack to get the result
        StringBuilder sb = new StringBuilder();
        while(! stack.isEmpty()) { sb.insert(0 , "/" + stack.pop());
        }
        return "".equals(sb.toString()) ? "/" : sb.toString();
    }
Copy the code

The test code

    public static void main(String[] args) {
        String path = "/a/./b/.. /.. /c/";
        new Number71().simplifyPath(path);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section