Algorithm
Problem Name: 71. Simplify Path
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 format 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 <= 3000pathconsists of English letters, digits, period'.', slash'/'or'_'.pathis a valid absolute Unix path.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char *dirname(char **path) {
char *start, *end;
start = *path;
while (*start && *start == '/') {
start ++;
}
if (!*start) return NULL;
end = start + 1;
while (*end && *end != '/') {
end ++;
}
if (*end) {
*end = 0;
end ++;
}
*path = end;
return start;
}
char* simplifyPath(char* path) {
char *buff, *p;
char **stack;
int sz, sp, i;
int len = strlen(path);
while (*path && *path != '/') path ++;
sz = 100;
stack = malloc(sz * sizeof(char *));
//assert(stack);
sp = 0;
#define PUSH(P) do { stack[sp ++] = P; } while (0)
#define POP() do { if (sp) stack[-- sp]; } while (0)
buff = calloc((len + 1), sizeof(char));
//assert(buff);
if (*path == '/') {
buff[0] = '/';
}
p = dirname(&path);
while (p) {
printf("%s, ", p);
if (*p == '.' && *(p + 1) == 0) {
// skip it
} else if (*p == '.' && *(p + 1) == '.' && *(p + 2) == 0) {
POP();
} else {
PUSH(p);
}
p = dirname(&path);
}
for (i = 0; i < sp; i ++) {
if (i) strcat(buff, "/");
strcat(buff, stack[i]);
}
free(stack);
return buff;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string simplifyPath(string path) {
string res, s;
stack < string>stk;
stringstream ss(path);
while(getline(ss, s, '/')) {
if (s == "" || s == ".") continue;
if (s == ".." && !stk.empty()) stk.pop();
else if (s != "..") stk.push(s);
}
while(!stk.empty()){
res = "/"+ stk.top() + res;
stk.pop();
}
return res.empty() ? "/" : res;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String simplifyPath(String path) {
Stack stack = new Stack<>();
String[] splits = path.split("/");
for (String split : splits) {
if (split.equals("") || split.equals(".")) {
continue;
} else if (split.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(split);
}
}
StringBuilder resultingPath = new StringBuilder();
while (!stack.isEmpty()) {
resultingPath.insert(0, stack.pop()).insert(0, "/");
}
return resultingPath.length() == 0 ? "/" : resultingPath.toString();
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const simplifyPath = function(path) {
path = path.split('/').filter(s => !!s && s !== '.')
while (path[0] === '..') path = path.slice(1)
let result = []
for (let val of path) {
if (val === '..') result.pop()
else result.push(val)
}
return '/' + result.join('/')
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def simplifyPath(self, path):
stack = []
for c in path.split("/"):
stack = stack[:-1] if c== ".." else stack + [c] if c and c != "." else stack
return "/" + "/".join(stack)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Text;
namespace LeetCode
{
public class _071_SimplifyPath
{
public string SimplifyPath(string path)
{
if (string.IsNullOrEmpty(path)) { return "/"; }
var folders = path.Split(new char[] { '/' }, StringSplitOptions.RemoveEmptyEntries);
var folder = string.Empty;
var builder = new StringBuilder();
var ignore = 0;
for (int i = folders.Length - 1; i >= 0; i--)
{
folder = folders[i];
if (folder.Equals(".")) { continue; }
if (folder.Equals("..")) { ignore++; continue; }
if (ignore > 0) { ignore--; continue; }
builder.Insert(0, folder);
builder.Insert(0, "/");
}
return builder.Length > 0 ? builder.ToString() : "/";
}
}
}
Input
Output