Dare2Solve
The problem requires simplifying a Unix-style file path. Unix-style paths use "/" as a directory separator, "." to represent the current directory, and ".." to move up one directory. We need to handle these special symbols appropriately and ignore unnecessary slashes to create the canonical path. This can be effectively managed using a stack data structure to keep track of the directories.
Initialize a Stack: Use a stack to keep track of directory names.
Split the Path: Split the input path by the "/" delimiter to process each part individually.
Process Each Part:
Build the Result Path: After processing all parts, join the elements in the stack with "/" to form the simplified path.
Edge Cases: Ensure the path starts with a single slash "/" and handle the root directory properly (the stack might be empty).
O(n), where n is the length of the input path. Each character is processed once.
O(n), where n is the length of the input path. In the worst case, the stack could contain all directory names from the path.
class Solution {
public:
string simplifyPath(string path) {
vector<string> stack;
stringstream ss(path);
string dir;
while (getline(ss, dir, '/')) {
if (dir == "." || dir.empty()) {
continue;
} else if (dir == "..") {
if (!stack.empty()) {
stack.pop_back();
}
} else {
stack.push_back(dir);
}
}
string result = "/";
for (int i = 0; i < stack.size(); ++i) {
result += stack[i];
if (i < stack.size() - 1) {
result += "/";
}
}
return result;
}
};
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
directories = path.split('/')
for dir in directories:
if dir == '.' or not dir:
continue
elif dir == '..':
if stack:
stack.pop()
else:
stack.append(dir)
return '/' + '/'.join(stack)
class Solution {
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] directories = path.split("/");
for (String dir : directories) {
if (dir.equals(".") || dir.isEmpty()) {
continue;
} else if (dir.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(dir);
}
}
StringBuilder result = new StringBuilder();
for (String dir : stack) {
result.append("/").append(dir);
}
return result.length() > 0 ? result.toString() : "/";
}
}
var simplifyPath = function (path) {
const stack = [];
const directories = path.split("/");
for (const dir of directories)
{
if (dir === "." || !dir)
{
continue;
} else if (dir === "..") {
if (stack.length > 0) {
stack.pop();
}
} else {
stack.push(dir);
}
}
return "/" + stack.join("/");
};