Stack - 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.

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

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.

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 <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path

Solution 1 - Using a stack and read character by character from path
Solution 2 - Using a stack and split the path string by '/'

In this approach, we will read character by character and construct the path element, when we see '/' apply the rules such as if the current path element is .. then remove the path element before that, and if the path path element is . just skip it (since it is pointing to current directory). We will use a Stack datastructure to store the path elements, so that it makes it easy to apply these path rules, for example if the path is something like this /abc/def/ghi/../../.. simplified path will become / (root directory).

Implementation steps:

First, declare two variables stack, a Stack that we will use to store path elements, and current a Sting to store current path element.
Next, loop through each character of path string and if current character is / or if we reach of end of path do the following :
- If the current value is .., and if the stack is not empty, then remove the top the element of stack and continue.
- If the current value is not empty, and if it is NOT equal to ., then add the current path element into stack.
- Reset the path to "" to empty, once we either do one of the above two steps.
If the current character is not /, then append the character to current string.
At the end, loop through stack elements, and create a new String with '/' separator.

import java.util.Stack; public class SimplifyPath { static String simplifyPath(String path) { Stack<String> stack = new Stack<>(); String current = ""; for(int i=0; i<=path.length(); i++) { // i<=path.length(), to handle what 'current' holds at the end loop if(i == path.length() || path.charAt(i) == '/') { //directory separator or end of path if("..".equals(current)) { if(!stack.isEmpty()) stack.pop(); // is stack is not empty remove it , otherwise ignore it } else if (!current.isEmpty() && !".".equals(current)) { stack.push(current); } current = ""; } else { current += path.charAt(i); } } return "/" + String.join("/", stack); } public static void main(String[] args) { System.out.println(simplifyPath("/../abc//./def")); System.out.println(simplifyPath("/abc/def/ghi/../../..")); } }

Complexity Analysis:

Time complexity: All the above operations runs in O(n) where n is the length of input string path.
Space complexity: O(n) for storing elements into stack.

In this approach, we will same approach as above, but instead of iterating through each character, we will use utility method String.split(regex) method using regular expression. '/'. (String's split() operation)

import java.util.Stack; public class SimplifyPath { static String simplyPathUsingStringSplit(String path) { Stack<String> stack = new Stack<>(); String[] tokens = path.split("/"); for(String token: tokens) { if("..".equals(token)) { if(!stack.isEmpty()) stack.pop(); } else if (!token.isEmpty() && !".".equals(token) && !"/".equals(token)) { stack.push(token); } } return "/"+String.join("/", stack); } public static void main(String[] args) { System.out.println(simplyPathUsingStringSplit("/../abc//./def")); System.out.println(simplyPathUsingStringSplit("/abc/def/ghi/../../..")); } }

Complexity Analysis:

Time complexity: All the above operations runs in O(n) where n is the length of input string path.
Space complexity: O(n) for storing elements into stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis:

Complexity Analysis: