[Daily Interview] -10 Simplify the path

The title

!!!!! Simplified path – force link

Analysis of the

This may seem complicated at first glance, but a closer look at a few examples reveals that there aren’t really many cases to deal with, except:

• null
• .
• .
• path

What to do with them? Compared to the valid parentheses problem, the first thing you can think of is using stacks to help us solve the problem:

• encounternull 或 ., do not do processing
• encounterpathThat will bepathInto the stack
• encounter.And out of the stack

This way, the code is easy to implement:

var simplifyPath = function (path) {

  const stack = [];

  const pathArr = path.split("/");

  for (let i = 0; i < pathArr.length; i++) {

    const p = pathArr[i];

    if (p === "..") {

      stack.pop();

    } else if (p === "." || p === "") {

      continue;

    } else {

      stack.push(p);

    }

  }

  return "/" + stack.join("/");

};

Copy the code

The results are as follows:

To optimize the

The above code does not look too ugly because there is not much logic to deal with. If we need to deal with additional logic, for example, if we encounter ~ and think it is /home/user, we will have to add additional conditional branches, and the code will gradually become big and messy and difficult to maintain.

Here we can use the strategy pattern to optimize:

var simplifyPath = function (path) {

  const stack = [];

  const pathArr = path.split("/");

  const strategy = {

    "": stack= > stack,

    ".": stack= > stack,

    "..": stack= > stack.pop()

  };



  for (let i = 0; i < pathArr.length; i++) {

    const p = pathArr[i];

    if (p in strategy) {

      strategy[p](stack);

    } else {

      stack.push(p);

    }

  }

  return "/" + stack.join("/");

};

Copy the code

The results are as follows: