Problem Statement: Simplify Path
You are given an absolute path for a file or directory in a Unix-style file system, where the path starts with a / (root directory) and can contain several subdirectories separated by /. The task is to simplify the given path by eliminating redundant parts and returning the canonical (simplified) path.
Rules:
- A path might contain the following:
"."which refers to the current directory and can be ignored.".."which means moving one level up in the directory structure.- Directories with names which should remain as part of the path.
- The final result should be an absolute path that begins with a
/and doesn’t contain unnecessary slashes or..
Example:
Input:
"/home/../usr/./bin"
Output:
"/usr/bin"
Explanation:
- The path starts at
/home, but..moves it one level up, so it moves to/. usris a directory, so/usris added..means the current directory, which does nothing.- Finally,
binis added, and the simplified path is/usr/bin.
Approach:
- Split the Path:
- Split the given path by
/. This will give us individual components like directory names,.(current directory), and..(parent directory).
- Split the given path by
- Use a Stack:
- Use a stack to simulate moving through directories. For each component:
- If it’s
"..", pop the top of the stack (move up one level). - If it’s
".", skip it (it doesn’t affect the path). - Otherwise, it’s a valid directory name, so push it onto the stack.
- If it’s
- Use a stack to simulate moving through directories. For each component:
- Rebuild the Simplified Path:
- After processing all components, the stack will contain the simplified path components.
- Join them with
/, and make sure the path starts with/.
- Edge Cases:
- Paths that contain only
"."or".."should resolve to the root directory. - Empty paths should return
/.
- Paths that contain only
Time Complexity:
- O(n) where
nis the length of the path. We are iterating through each component once.
Space Complexity:
- O(n) in the worst case, where
nis the number of components in the path (because we are using a stack to store the components).
Code Implementations:
1. C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* simplifyPath(char* path) {
char* result = (char*)malloc(sizeof(char) * (strlen(path) + 1));
char* stack[1000];
int top = -1;
// Split the path by '/'
char* token = strtok(path, "/");
while (token != NULL) {
if (strcmp(token, ".") == 0 || strlen(token) == 0) {
// Skip current directory and empty strings
} else if (strcmp(token, "..") == 0) {
// Pop from stack (go up one directory)
if (top >= 0) {
top--;
}
} else {
// Push directory to stack
stack[++top] = token;
}
token = strtok(NULL, "/");
}
// Rebuild the path
if (top == -1) {
result[0] = '/';
result[1] = '\0';
return result;
}
int index = 0;
for (int i = 0; i <= top; i++) {
result[index++] = '/';
strcpy(result + index, stack[i]);
index += strlen(stack[i]);
}
result[index] = '\0';
return result;
}
int main() {
char path[] = "/home/../usr/./bin";
char* simplifiedPath = simplifyPath(path);
printf("Simplified Path: %s\n", simplifiedPath);
free(simplifiedPath);
return 0;
}
2. C++
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
string simplifyPath(string path) {
vector<string> stack;
stringstream ss(path);
string token;
// Split the path by '/'
while (getline(ss, token, '/')) {
if (token == "" || token == ".") {
// Skip empty strings and current directory
} else if (token == "..") {
// Move up one directory
if (!stack.empty()) {
stack.pop_back();
}
} else {
// Push directory to stack
stack.push_back(token);
}
}
// Rebuild the path
if (stack.empty()) return "/";
string result = "";
for (const string& dir : stack) {
result += "/" + dir;
}
return result;
}
int main() {
string path = "/home/../usr/./bin";
cout << "Simplified Path: " << simplifyPath(path) << endl;
return 0;
}
3. Java
import java.util.*;
public class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new LinkedList<>();
String[] components = path.split("/");
for (String component : components) {
if (component.equals("") || component.equals(".")) {
// Skip empty or current directory
} else if (component.equals("..")) {
// Pop from stack (go up one directory)
if (!stack.isEmpty()) {
stack.pollLast();
}
} else {
// Push directory to stack
stack.offerLast(component);
}
}
if (stack.isEmpty()) {
return "/";
}
// Rebuild the path
StringBuilder result = new StringBuilder();
for (String dir : stack) {
result.append("/").append(dir);
}
return result.toString();
}
public static void main(String[] args) {
Solution sol = new Solution();
String path = "/home/../usr/./bin";
System.out.println("Simplified Path: " + sol.simplifyPath(path));
}
}
4. Python
def simplifyPath(path: str) -> str:
stack = []
components = path.split("/")
for component in components:
if component == "" or component == ".":
# Skip empty or current directory
continue
elif component == "..":
# Move up one directory
if stack:
stack.pop()
else:
# Push directory to stack
stack.append(component)
# Rebuild the path
return "/" + "/".join(stack) if stack else "/"
# Test
path = "/home/../usr/./bin"
print("Simplified Path:", simplifyPath(path))
5. C#
using System;
using System.Collections.Generic;
public class Solution {
public string SimplifyPath(string path) {
Stack<string> stack = new Stack<string>();
string[] components = path.Split('/');
foreach (var component in components) {
if (component == "" || component == ".") {
// Skip empty or current directory
continue;
} else if (component == "..") {
// Pop from stack (go up one directory)
if (stack.Count > 0) {
stack.Pop();
}
} else {
// Push directory to stack
stack.Push(component);
}
}
if (stack.Count == 0) {
return "/";
}
// Rebuild the path
List<string> result = new List<string>();
while (stack.Count > 0) {
result.Insert(0, stack.Pop());
}
return "/" + string.Join("/", result);
}
public static void Main() {
Solution sol = new Solution();
string path = "/home/../usr/./bin";
Console.WriteLine("Simplified Path: " + sol.SimplifyPath(path));
}
}
6. JavaScript
function simplifyPath(path) {
const stack = [];
const components = path.split("/");
for (let component of components) {
if (component === "" || component === ".") {
// Skip empty or current directory
continue;
} else if (component === "..") {
// Pop from stack (go up one directory)
if (stack.length > 0) {
stack.pop();
}
} else {
// Push directory to stack
stack.push(component);
}
}
// Rebuild the path
return stack.length === 0 ? "/" : "/" + stack.join("/");
}
// Test
let path = "/home/../usr/./bin";
console.log("Simplified Path:", simplifyPath(path));
Summary:
The algorithm involves splitting the input path into components and using a stack to simulate directory navigation. By processing each component, we can effectively simplify the path.
- Time complexity: O(n) where
nis the length of the path. - Space complexity: O(n) for the stack used to hold components of the path.
This approach ensures that we handle edge cases like repeated slashes, . (current directory), and .. (parent directory) correctly.