71. Simplify Path

Description

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

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "/home/"

Output: "/home"

Explanation: Note that there is no trailing slash after the last directory name.

Example 2

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.

Example 3

Input: "/home//foo/"

Output: "/home/foo"

Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4

Input: "/a/./b/../../c/"

Output: "/c"

Example 5

Input: "/a/../../b/../c//.//"

Output: "/c"

Example 6

Input: "/a//b////c/d//././/.."

Output: "/a/b/c"

Solutions

Solution 1

/**
 * 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(): "/";
    }
}

Follow up

• Program for longest common directory path - GFG