Sponsored
This approach utilizes a stack data structure to process the path components. By splitting the path on the '/' character, we collect the different components of the path. Using a stack helps efficiently manage directory movement due to '..'. For every directory name, it is pushed to the stack, for '..' we pop from the stack, and '.' is simply ignored. After processing all components, we join the names in the stack with '/' to form the simplified canonical path.
Time Complexity: O(N) where N is the length of the path string, as we perform operations linearly along the string.
Space Complexity: O(N) because we use a stack that can contain each part of the path in the worst case.
1#include <iostream>
2#include <sstream>
3#include <string>
4#include <vector>
5using namespace std;
6
7string simplifyPath(string path) {
8 vector<string> stack;
9 stringstream ss(path);
10 string token;
11
12 while (getline(ss, token, '/')) {
13 if (token == "..") {
14 if (!stack.empty()) {
15 stack.pop_back();
16 }
17 } else if (token != "." && !token.empty()) {
18 stack.push_back(token);
19 }
20 }
21
22 string result;
23 for (const string &dir : stack) {
24 result += "/" + dir;
25 }
26
27 return result.empty() ? "/" : result;
28}The C++ solution makes use of the standardized 'stringstream' to tokenize the input path string. We read each token split by '/', and decide whether to ignore it, go up a directory (pop the stack), or consider it as a part of the path (push to the stack). The canonical path is formed by concatenating stack elements with '/'.
This approach optimizes the simplification process using string handling techniques without explicitly using stack structures. It involves maintaining a result string directly, with an index pointer to simulate stack behavior. Iterating over path components allows addition, removal, or skipping of segments based on path rules, with a focus on reducing stack overhead. Finally, the result string is reconstructed as the simplified path.
Time Complexity: O(N) as parsing occurs once through entire path.
Space Complexity: O(N) utilized for the resultant path string (no explicit stack).
1
public class Solution {
public string SimplifyPath(string path) {
StringBuilder result = new StringBuilder();
string[] components = path.Split(new char[] {'/'}, StringSplitOptions.RemoveEmptyEntries);
foreach (string component in components) {
if (component == "..") {
if (result.Length > 0) {
int lastSlashIndex = result.ToString().LastIndexOf('/');
result.Remove(lastSlashIndex, result.Length - lastSlashIndex);
}
} else if (component != ".") {
result.Append("/").Append(component);
}
}
return result.Length > 0 ? result.ToString() : "/";
}
}C# optimizes through using StringBuilder for direct manipulation of sequences of directories. By replacing stack operations with index-managed result strings, this method streamlines the transformation into canonical form.