This is the 9th day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021.

The title

Link: leetcode-cn.com/problems/si…

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.

Example 2:

Enter: path = “/.. /” Output: “/” Explanation: Going one step up from the root directory is not feasible because the root directory is the highest level you can reach.

Example 3:

Input: path = “/home//foo/” Output: “/home/foo” Explanation: In a canonical path, multiple consecutive slashes need to be replaced with a single slash.

Example 4:

Enter: path = “/a/./b/.. /.. /c/” output:

 

Tip:

  • 1 <= path.length <= 3000
  • pathIt consists of letters, numbers,'. '.'/' 或 '_'Composition.
  • pathIs a valid Unix-style absolute path.

Their thinking

Idea 1

Split path into arrays with ‘/’, such as /a/./b/.. /.. / c/split into [‘, ‘a’, ‘. ‘, ‘b’, ‘. ‘, ‘. ‘, ‘c’, ‘]. Create a new stack for the current path and iterate through the array elements after path split:

  • When you encounter a normal letter, push instack 中
  • encounter.When,stackThe latest path is displayed
  • encounter.If the value is null, the current stack is not modified.
  • The last return'/' + stack.join('/')Is the new path
var simplifyPath = function(path) {
    const stack = [];
    const pathArr = path.split('/');
    
    for (let item of pathArr) {
        if (item === ' ' || item === '. ') {
            continue;
        } else if (item === '.. ') {
            stack.pop();
        } else{ stack.push(item); }}return '/' + stack.join('/');
};
Copy the code

Idea 2

Order of the stack

  • Unix style

    • A point (.), indicating the current directory.
    • Two points (.) indicates the upper-level directory.
    • Continuous slashes (/)

  • Standardize the path

    • In order to/At the beginning
    • There is only one slash between two directories.
    • Last directory name (if present), not/At the end.
    • Unix-style shortest string ()

  • Split the Unix path into an array of strings using the arr.split() method, separated by a slash (/).

  • Pushes strings sequentially onto the stack

  • Contains no elements, one point (.) “, skip.

  • Two points (..) , moves the current top element off the stack.

/ * * *@param {string} path
 * @return {string}* /
class Stack {
    constructor() {
        this._top = 0;
        this._data = [];
    }
    push(element) {
        this._top ++;
        return this._data.push(element);
    }
    pop() {
        this._top --;
        return this._data.pop();
    }
    join(symbol) {
        this._top = 1;
        return this._data.join(symbol); }}var simplifyPath = function(path) {
    let stack = new Stack();
    let pathArr = path.split('/');
    for (let eachStr of pathArr) {
        if (eachStr == ' ' || eachStr == '. ') {
            continue;
        } else if (eachStr == '.. ') {
            stack.pop();
        } else{ stack.push(eachStr); }}return '/' + stack.join('/');
}
Copy the code
Complexity analysis
  • Time complexity: O(n),n = path.split('/').length .
    • forLoop through the arraypath.split('/') .
    • In this case, the time complexity of the method arr.push() arr.pop() is O(1) and that of arr.join() string.split() is O(n).
  • Space complexity: O(n),n = path.split('/').length .
    • An array ofpathArrLength ofn = path.split('/').length .
    • In this case, the spatial complexity of the method arr.push() arr.pop() is O(1) and that of arr.join() string.split() is O(n).

The length of the array

  • JavaScript arrays can be unlimited in length, as long as memory allows. The initial length of the array can be set and then automatically increased if desired. Using a number string as an index of an array is equivalent to using a number index directly.

  • A JavaScript array is actually a key-value pair. A Key can be a number as well as other objects.

var arr = new Array(2);
  arr[0] = 1;
  arr['second'] = 2;
  arr['third'] = 3;
  console.log(arr['0'] + ' ' + arr['second'] + [' '] + arr['third']);
  console.log(arr.length);
  /** * console: 1 2 3 2 */
Copy the code

Idea 3

Chain stack

/ * * *@param {string} path
 * @return {string}* /
class Node {
    constructor (element) {
        this.element = element
        this.next = null}}class Stack {
    constructor() {
        this._top = null;
    }
    push(element) {
        let node = new Node(element);
        if (this._top == null) {
            this._top = node;
        } else {
            node.next = this._top;
            this._top = node; }}pop() {
        if (this._top == null) {
            return -1;
        }
        let element = this._top.element;
        this._top = this._top.next;
        element = null;
    }
    display() {
        let res = ' ';
        if (this._top ! =null) {
            let tmp = this._top;
            res = tmp.element;
            tmp = tmp.next;
            while(tmp ! =null) {
                res = tmp.element + '/'+ res; tmp = tmp.next; }}return '/'+ res; }}var simplifyPath = function(path) {
    let stack = new Stack();
    let pathArr = path.split('/');
    for (let eachStr of pathArr) {
        if (eachStr == ' ' || eachStr == '. ') {
            continue;
        } else if (eachStr == '.. ') {
            stack.pop();
        } else{ stack.push(eachStr); }}return stack.display();
}
Copy the code