Given an absolute pathname that may have . or .. as part of it, return the shortest standardized path

Given an absolute pathname that may have . or .. as part of it, return the shortest standardized path. For example, given “/usr/bin/../bin/./scripts/../”, return “/usr/bin/”.

To obtain the shortest standardized path from an absolute pathname that may contain “.” or “..” as part of it, you can follow these steps:

1. Split the absolute pathname by “/” to separate the directories and store them in a list.
2. Initialize an empty stack.
3. Iterate through the directories in the list:
   • If the current directory is “.”, simply continue to the next iteration.
   • If the current directory is “..”:
     • If the stack is not empty, pop the top element from the stack (to go up one level in the directory hierarchy).
     • If the stack is empty, continue to the next iteration.
   • If the current directory is neither “.” nor “..”, push it onto the stack.
4. Construct the standardized path by joining the elements in the stack with “/” as the separator.

Here’s an example Python code that implements this logic:

Solution – Python

def shortest_standardized_path(path):
    directories = path.split("/")
    stack = []

    for directory in directories:
        if directory == "." or directory == "":
            continue
        elif directory == "..":
            if stack:
                stack.pop()
        else:
            stack.append(directory)

    standardized_path = "/" + "/".join(stack)
    return standardized_path or "/"

# Example usage:
path = "/usr/bin/../bin/./scripts/../"
print(shortest_standardized_path(path))  # Output: /usr/bin/

Java – Solution

import java.util.*;

public class ShortestStandardizedPath {
    public static String shortestStandardizedPath(String path) {
        Deque<String> stack = new ArrayDeque<>();

        String[] directories = path.split("/");
        for (String directory : directories) {
            if (directory.equals(".") || directory.isEmpty()) {
                continue;
            } else if (directory.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(directory);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append("/").append(stack.removeLast());
        }

        return sb.length() == 0 ? "/" : sb.toString();
    }

    public static void main(String[] args) {
        String path = "/usr/bin/../bin/./scripts/../";
        System.out.println(shortestStandardizedPath(path));  // Output: /usr/bin/
    }
}

Solution – Javascript

function shortestStandardizedPath(path) {
    const directories = path.split("/");
    const stack = [];

    for (const directory of directories) {
        if (directory === "." || directory === "") {
            continue;
        } else if (directory === "..") {
            if (stack.length !== 0) {
                stack.pop();
            }
        } else {
            stack.push(directory);
        }
    }

    const standardizedPath = "/" + stack.join("/");
    return standardizedPath || "/";
}

const path = "/usr/bin/../bin/./scripts/../";
console.log(shortestStandardizedPath(path));  // Output: /usr/bin/