Simplify a File Path
Problem
Each line is an absolute Unix path (it starts with /). Print its simplest form: . means the same folder and is dropped, .. means go to the parent folder (at the root it does nothing), several slashes in a row count as one, and there is no slash at the end (except for the root path /). Names such as ... or ..hidden are normal folder names.
Constraints
- 1 <= lines <= 10^4
- Each path starts with /
Examples
Input
/home/ /a/./b/../../c/
Output
/home /c
Solutions
Paths from users or files must be cleaned before use, otherwise ../ can escape the folder you meant to allow (a path traversal attack). Real code should use Path.normalize (Java), path.posix.normalize (Node) or pathlib (Python) and also check the result against the allowed base folder.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One simple path per line.
* Approach: Absolute paths.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
String[] output = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
// Step 1: A stack holds the folder names of the path so far.
java.util.ArrayDeque<String> stack = new java.util.ArrayDeque<>();
for (String name : lines[i].split("/")) {
if (name.isEmpty() || name.equals(".")) {
// Step 2: Empty names (double slashes) and "." change nothing.
continue;
}
if (name.equals("..")) {
// Step 3: ".." removes the last folder, if there is one.
if (!stack.isEmpty()) {
stack.removeLast();
}
} else {
stack.addLast(name);
}
}
// Step 4: Join the names with slashes. The root path stays "/".
output[i] = "/" + String.join("/", stack);
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why is cleaning .. important for security?