Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
Constraints
Approach
Links
YouTube
Examples
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Input: "/../"
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: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Input: "/a/./b/../../c/"
Output: "/c"
Input: "/a/../../b/../c//.//"
Output: "/c"
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
Solutions
/**
* Time complexity : O(N) if there are N characters in the original path.
* First, we spend O(N) trying to split the input path into components
* and then we process each component one by one which is again an O(N)
* operation. We can get rid of the splitting part and just string together
* the characters and form directory names etc. However, that would be too
* complicated and not worth depicting in the implementation. The main idea
* of this algorithm is to use a stack. How you decide to process the input
* string is a personal choice.
* Space complexity : O(N). Actually, it's 2N because we have the array that
* contains the split components and then we have the stack.
*/
class Solution {
public String simplifyPath(String path) {
if(path == null || path.isEmpty()) return "";
String[] components = path.split("/");
Stack<String> stack = new Stack<String>();
for(String directory: components) {
if(directory.isEmpty() || directory.equals(".")) {
continue;
} else if(directory.equals("..")) {
if(!stack.isEmpty()) {
stack.pop();
}
} else {
stack.add(directory);
}
}
StringBuilder result = new StringBuilder();
for(String dir: stack) {
result.append("/");
result.append(dir);
}
return result.length() > 0? result.toString(): "/";
}
}