How to Solve ‘SimplifyPath’ in CodeFights

The Problem:

Given an absolute file path (Unix-style), shorten it to the format /<dir1>/<dir2>/<dir3>/....

Here is some info on Unix file system paths:

  • / is the root directory; the path should always start with it even if it isn’t there in the given path;
  • / is also used as a directory separator; for example, /code/fights denotes a fights subfolder in the code folder in the root directory;
    • this also means that // stands for “change the current directory to the current directory”
  • . is used to mark the current directory;
  • .. is used to mark the parent directory; if the current directory is root already, .. does nothing.

Example

For path = "/home/a/./x/../b//c/", the output should be
simplifyPath(path) = "/home/a/b/c".

Here is how this path was simplified:
* /./ means “move to the current directory” and can be replaced with a single /;
* /x/../ means “move into directory x and then return back to the parent directory”, so it can replaced with a single /;
* // means “move to the current directory” and can be replaced with a single /.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string pathA line containing a path presented in Unix style format. All directories in the path are guaranteed to consist only of English letters.

    Constraints:
    1 ≤ path.length ≤ 5 · 104.

  • [output] stringThe simplified path.

The Solution:

asddasdasdas15

The Explanation:

First of all, we need the segments in the path, separated by ‘/’s.

For each of these, we will decide what we are going to do. First rule, it always starts at the root. Second, ‘.’ is useless. Third, ‘..’ goes back one level, unless we are already at root. Empty means we stay at the same level, that is, useless. So, we can keep a stack, and every time we see any of these special segments, we apply the operation needed. In this case, we only need to go one level up, by popping the top element from the stack, or doing nothing. At the end, we just merge all the elements we have in the stack, with the delimiter ‘/’.

Also, a better way to do this would be to join them using “/” join.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s