# Nhut Nguyen # Problem statement

Given a string `path`, which is an absolute path (starting with a slash `'/'`) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period `'.'` refers to the current directory, a double period `'..'` refers to the directory up a level, and any multiple consecutive slashes (i.e. `'//'`) are treated as a single slash `'/'`. For this problem, any other formats of periods such as `'...'` are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash `'/'`.
• Any two directories are separated by a single slash `'/'`.
• The path does not end with a trailing `'/'`.
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period `'.'` or double period `'..'`).

Return the simplified canonical path.

## Example 1

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

## Example 2

``````Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
``````

## Example 3

``````Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
``````

## Constraints

• `1 <= path.length <= 3000`.
• `path` consists of English letters, digits, period `'.'`, slash `'/'` or `'_'`.
• `path` is a valid absolute Unix path.

# Solution: Using the property LIFO of a stack to handle directory `".."`

Following the format constraints, you can store the directories' names in a stack. With its LIFO property, the last directory can be removed whenever the directory `".."` appears next.

## Code

``````#include <iostream>
#include <vector>
using namespace std;
string simplifyPath(string path) {
vector<string> s;
string dir;
for (char c : path) {
if (c != '/') {
dir += c;
continue;
}
if (dir == "..") {
if (!s.empty()) {
s.pop_back();
}
} else if (!dir.empty() && dir != ".") {
s.push_back(dir);
}
dir = "";
}
if (dir == "..") {
if (!s.empty()) {
s.pop_back();
}
} else if (!dir.empty() && dir != ".") {
s.push_back(dir);
}
dir = "";
for (auto d : s) {
dir += "/" + d;
}
return dir == "" ? "/" : dir;
}
int main() {
cout << simplifyPath("/home/") << endl;
cout << simplifyPath("/a/..") << endl;
cout << simplifyPath("/a//b////c/d//././/..") << endl;
cout << simplifyPath("/../") << endl;
cout << simplifyPath("/a/./b/../../c/") << endl;
}
``````
``````Output:
/home
/
/a/b/c
/
/c
``````

## Complexity

• Runtime: `O(N)`, where `N = path.length`.
• Extra space: `O(N)`.

# Implementation notes

As the property LIFO of a stack is used, you can use `std::stack` to implement the algorithm. But here are the reasons you can use `std::vector` for this purpose as well.

1. `std::vector` also supports `pop_back()` and `push_back()` like a `std::stack`.
2. It is clearer to go from the root directory to the children ones with `std::vector` when building the canonical path from the simplified directories at the end of the algorithm.

On the other hand, in the solution above, a piece of code is duplicated to add the last directory to the stack.

One way to avoid it is by adding a slash `'/'` at the end of the `path` to force it ends with `'/'`. Then the duplicated code is handled inside the loop as well.

## Code

``````#include <iostream>
#include <vector>
using namespace std;
string simplifyPath(string path) {
path += "/";
vector<string> s;
string dir;
for (char c : path) {
if (c != '/') {
dir += c;
continue;
}
if (dir == "..") {
if (!s.empty()) {
s.pop_back();
}
} else if (!dir.empty() && dir != ".") {
s.push_back(dir);
}
dir = "";
}
dir = "";
for (auto d : s) {
dir += "/" + d;
}
return dir == "" ? "/" : dir;
}
int main() {
cout << simplifyPath("/home/") << endl;
cout << simplifyPath("/a/..") << endl;
cout << simplifyPath("/a//b////c/d//././/..") << endl;
cout << simplifyPath("/../") << endl;
cout << simplifyPath("/a/./b/../../c/") << endl;
}
``````
``````Output:
/home
/
/a/b/c
/
/c
``````

## Complexity

• Runtime: `O(N)`, where `N = path.length`.
• Extra space: `O(N)`.