• This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together

  • LeetCode: 71

    • Time: 2022-01-06
    • Strength button difficulty: Medium
    • Personal difficulty: Easy
    • Data structure: string, stack
    • Algorithm: analog, double pointer

2022-01-06: LeetCode: 71. Simplified path

1. Topic description

  • Title: Original title link

    • You are given the string path, which represents the uniX-style absolute path to a file or directory/To start, convert this to a more concise canonical path
    • In uniX-style file systems, a point.Represents the current directory itself
    • In addition, two points.Indicates that the directory is switched to the parent directory. Both can be part of a complex relative path
    • Any number of consecutive slashes, such as://Are treated as single slashes/For this problem, any point of any other format (e.g.,.) are treated as file or 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/
      • The last directory name (if present) cannot be entered/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, no.or.
    • Returns the simplified canonical path

  • Input output specification

    • Enter: string path
    • Output: Simplified string

  • Input and output examples

    • Input: “/.. /I/./love//996/.. /you/”
    • Output: “/ / I love you”
    • Input: “/ a /. / / b.. /.. /c/”
    • Output: “/ c”

2. Method 1: string simulation + stack

  • Train of thought

    • C) traversing the entire string. D) traversing the entire string/,.,.And so on
    • Finally, concatenate the subdirectory paths that meet toStringBuilderIn the
    • Pay attention to.When switching to the parent directory, you need to check whether the root directory is reached. If so, the output is displayed/

  • Complexity analysis: n is the length of the path string

    • Time complexity: O(n)O(n)O(n), traverses the entire path string, and also traverses the List of subdirectories in the final output
    • Space complexity: O(n)O(n)O(n), uses a List set to store subpaths

  • Answer key

    public String simplifyPath(String path) {
    if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
    List<String> pathList = new ArrayList<>();
    int n = path.length();
    for (int i = 0; i < n; ) {
        if (path.charAt(i) == '/') { / / processing / / /
            i++; 
        } else {
            // Record the current location
            int index = i;
            while(i < n && path.charAt(i) ! ='/') {
                i++;
            }
            // Intercept a subdirectory
            String subPath = path.substring(index, i);
            / / processing [..]
            if ("..".equals(subPath)) {
                if(! pathList.isEmpty()) { pathList.remove(pathList.size() -1);
                }
                [.] [//]
            }else if (!".".equals(subPath) && !"".equals(subPath))
                // Store to subdirectory
                pathList.add(subPath);
        }
    }
    StringBuilder sb = new StringBuilder();
    if(! pathList.isEmpty()) {for(String subPath : pathList)
            sb.append("/").append(subPath);
    }
    return "".equals(sb.toString()) ? "/" : sb.toString();
}
Copy the code

3. Method 2: string splitting + stack

  • Train of thought

    • Similar to method 1, in addition to using a List collection, you can also use a stack structure to hold subdirectories
    • Use the string splitting methodsplit()Instead of traversing the entire path string, you just need to traverse the partitioned array of strings
    • Since the stack is first in last out (FILO), use a double-ended queue, such asLinkedListTo facilitate the operation of concatenating simplified strings at the end

  • Complexity analysis: n is the length of the path string

    • Time complexity:
      O ( n ) O(n)       , segmentation methodsplit()It actually traverses the entire path string
    • Space complexity: O(n)O(n)O(n), uses a stack structure to store subpaths

  • Answer key

    public String simplifyPath(String path) {
    if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
    Deque<String> stack = new LinkedList<>();
    String[] strs = path.split("/");
    for (String str : strs) {
        if ("..".equals(str)) {
            if (!stack.isEmpty()) {
                stack.removeLast();
            }
        } else if (!".".equals(str) && !"".equals(str)) {
            stack.offerLast(str);
        }
    }
    StringBuilder sb = new StringBuilder();
    while(! stack.isEmpty()) { sb.append("/").append(stack.removeFirst());
    }
    return "".equals(sb.toString()) ? "/" : sb.toString();
}
Copy the code

  • Thinking and Optimizing

    • Consider: how to concatenate simplified strings directly in a loop, instead of storing all subdirectories in a stack or collection and then iterating through the collection to concatenate strings
    • Optimization: Use two Pointersstart,endTo record the start and end positions of each concatenated string, if later encountered.Deletes the contents of the string based on a pointer
    • Because there could be more than one., so two Pointersstart,endAlso needs to be represented as the type of collection, respectively

  • Solution: Optimized version

    public String simplifyPath(String path) {
    if (path == null || path.length() == 0 || path.charAt(0) != '/') return null;
    StringBuilder sb = new StringBuilder();
    // Start and end Pointers
    Stack<Integer> start = new Stack<>();
    Stack<Integer> end = new Stack<>();
    / / initialization
    start.push(0);
    end.push(1);
    String[] strs = path.split("/");
    for (String str : strs) {
        / / processing [..]
        if ("..".equals(str)) { 
            if(! start.isEmpty()) { sb.delete(start.pop(), end.pop()); }else {
                sb.delete(0.1);
            }
            [.] [//]
        } else if (!".".equals(str) && !"".equals(str)) {  
            start.push(sb.length());
            sb.append("/").append(str); end.push(sb.length()); }}return "".equals(sb.toString()) ? "/" : sb.toString();
}
Copy the code

The last

LeetCoder, a new developer, has published some problem solving solutions based on other developers’ ideas (links to resources are at the bottom). Please follow me if this article helps. I hope you can give me three even “like” & “favorites” & “attention” ~ ~ ~ also hope you have time to visit my “personal blog”.