71. Simplify Path

MediumStackString
Leetcode Link

Problem Description

In the given problem, we are asked to take an absolute path for a file or directory in a Unix-style file system and convert it to a simplified canonical path.

An absolute path is a full path from the root of the file system and starts with a slash ('/'). The path may contain several special components:

  • A single period (.) represents the current directory.
  • A double period (..) represents moving up one directory level.
  • Multiple consecutive slashes (//) are considered identical to a single slash (/).

The goal is to take such a path and simplify it according to the rules of Unix file systems so that:

  • The simplified path must begin with a single slash (/).
  • Each pair of directories must be separated by a single slash (/).
  • The path must not end with a trailing slash (/).
  • The path should not contain any . or .., as they should be resolved to actual directories on the path from the root to the target.

For example, given the path "/a//b////c/d//././/..", the simplified canonical path would be "/a/b/c".

Intuition

The intuition behind the solution involves using a stack to process each component of the path from left to right. A stack is ideal for this task because it allows us to add and remove directories in the correct order - the last directory we moved into is the first one we'll move out of when we encounter a .. directive.

Here is how we can break down the problem and use a stack to solve it:

  1. Split the path by slashes, which gives us a list of directory names and other components like . and ... We can then iterate through this list.
  2. Ignore any empty strings resulting from consecutive slashes, as well as any . components, since they don't change the current directory.
  3. If a .. is encountered, check if there are any directories in the stack that we can "move up" from. If the stack is not empty, we pop the last directory off, effectively moving up a directory level.
  4. Add any other directory names to the stack, as they represent moving into a new directory.
  5. Once we've processed all components of the path, we combine the directories in the stack to form the simplified canonical path. To adhere to Unix-style paths, we ensure that the path begins with a slash and each directory is separated by a single slash.
  6. We do not add a trailing slash, because the canonical path format specifies that the path should not end with one.

Using this approach allows us to handle complex, redundant, or relative paths and convert them into their simplest form, which is the essence of simplifying a canonical path in a Unix-style file system.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The implementation of this solution relies on using a stack data structure, which fits perfectly for scenarios where we need to process items in a last-in, first-out manner. In the context of file paths, this method is beneficial for handling directories and the .. component that implies moving up one directory level. Below is the step-by-step breakdown of the algorithm based on the solution approach given:

  1. The path is split into components using the '/' as a delimiter using the split() function, which gives us a list of directories and possibly some '.' and '..' components.

  2. An empty stack stk is initialized to keep track of the directory names that we encounter as we iterate through the list of path components.

  3. We begin iterating over each component from the list. There are a few possible cases for each component s:

    • If s is an empty string or '.', which can happen if we have consecutive slashes or a period that represents the current directory, we do nothing and continue to the next component.
    • If s is '..', we check if there is anything in the stack. If the stack is not empty, which means there are previous directories we can move up from, we pop() the top element from the stack.
    • For all other cases, the component s is a directory name and is pushed onto the stack using append(s).

  4. After processing all components, we need to construct the canonical path from the elements in the stack. We do this by joining the elements of the stack with a '/' delimiter between them and prepend a '/' to represent the root directory, ensuring that our resulting path correctly starts with a single slash.

The final return statement '/' + '/'.join(stk) effectively builds our simplified canonical path from the stack. It's important to note that the stack enables us to handle backtrack operations caused by '..' components efficiently, allowing us to simplify the path correctly as we iterate through the components only once. This solution ensures that we avoid any redundant or unnecessary operations and achieve a clean, concise path as the output.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Example Walkthrough

Let's apply the solution approach to a small example path: "/home//foo/./bar/../baz/"

According to the approach:

  1. Split the path by slashes to get the components: ["home", "", "foo", ".", "bar", "..", "baz", ""].

  2. Initialize an empty stack stk: [].

  3. Iterate over each component:

    • Skip "" and ".".
    • home: Push onto the stack ["home"].
    • foo: Push onto the stack ["home", "foo"].
    • bar: Push onto the stack ["home", "foo", "bar"].
    • ..: Pop from the stack to get ["home", "foo"].
    • baz: Push onto the stack ["home", "foo", "baz"].
    • Skip "" at the end, since the path should not end with a trailing slash.

  4. Construct the canonical path by joining the elements in the stack with '/', and prepend a '/' to the result. The canonical path is "/home/foo/baz".

  5. Return the final simplified canonical path: "/home/foo/baz".

In this example, the stack has allowed us to keep track of the directories we have moved into and efficiently handle the case when we needed to move back up a directory due to the ".." component. The resulting path follows all the rules for a simplified canonical path and gives us the correct simple path from a more complex and redundant one.

Solution Implementation

1class Solution:
2    def simplifyPath(self, path: str) -> str:
3        # Initialize an empty list to use as a stack
4        stack = []
5      
6        # Split the path by "/", iterate over each part
7        for part in path.split('/'):
8            # If the part is an empty string or a ".", simply continue to the next part
9            if not part or part == '.':
10                continue
11            # If the part is "..", pop from the stack if it's not empty
12            elif part == '..':
13                if stack:
14                    stack.pop()
15            # Otherwise, add the part to the stack
16            else:
17                stack.append(part)
18      
19        # Join the stack elements to form the simplified path and prepend with "/"
20        simplified_path = '/' + '/'.join(stack)
21        return simplified_path
22
1class Solution {
2    public String simplifyPath(String path) {
3        // Use a deque as a stack to hold the directory names.
4        Deque<String> stack = new ArrayDeque<>();
5
6        // Split the path by "/" and iterate over the segments.
7        for (String segment : path.split("/")) {
8            // If the segment is empty or a single ".", just ignore it.
9            if (segment.isEmpty() || ".".equals(segment)) {
10                continue;
11            }
12            // If the segment is "..", pop an element from the stack if available.
13            if ("..".equals(segment)) {
14                if (!stack.isEmpty()) {
15                    stack.pollLast();
16                }
17            } else {
18                // Push the directory name onto the stack.
19                stack.offerLast(segment);
20            }
21        }
22      
23        // Join all the elements in the stack with "/", prepended by a "/" to form the simplified path.
24        String simplifiedPath = "/" + String.join("/", stack);
25      
26        // Return the simplified absolute path.
27        return simplifiedPath;
28    }
29}
30
1class Solution {
2public:
3    // Function to simplify the given Unix-like file path.
4    string simplifyPath(string path) {
5        deque<string> directoryNames; // Use a deque to store the directory names after parsing.
6        stringstream ss(path); // Create a stringstream to separate the elements by '/'.
7        string token; // String to store the separated elements.
8
9        // Process each part of the path separated by '/'.
10        while (getline(ss, token, '/')) {
11          
12            // Continue if the element is empty or a dot, which means stay in the current directory.
13            if (token == "" || token == ".") {
14                continue;
15            }
16          
17            // If element is a double dot, move up to the parent directory if possible.
18            if (token == "..") {
19                // Only pop if the stack is not empty (cannot go above root).
20                if (!directoryNames.empty()) {
21                    directoryNames.pop_back();
22                }
23            } else {
24                // Otherwise, it's a valid directory name; add to our list.
25                directoryNames.push_back(token);
26            }
27        }
28
29        // If directory stack is empty, we're at root.
30        if (directoryNames.empty()) {
31            return "/";
32        }
33
34        // Build the simplified path from the directory stack.
35        string result;
36        for (const auto& dirName : directoryNames) {
37            result += "/" + dirName; // Prefix each directory name with a slash.
38        }
39
40        // Return the final simplified path.
41        return result;
42    }
43};
44
1function simplifyPath(path: string): string {
2    // Initialize an empty stack to store the parts of the simplified path
3    const pathStack: string[] = [];
4
5    // Split the input path by '/' and iterate through the segments
6    for (const segment of path.split('/')) {
7        // Skip empty segments and current directory references '.'
8        if (segment === '' || segment === '.') {
9            continue;
10        }
11        // If segment is the parent directory reference '..'
12        if (segment === '..') {
13            // Pop the last element from the stack if it's not empty
14            if (pathStack.length) {
15                pathStack.pop();
16            }
17        } else {
18            // Push the current directory segment onto the stack
19            pathStack.push(segment);
20        }
21    }
22
23    // Join the stack elements with '/' to form the simplified path
24    // Ensure to start the path with the root directory '/'
25    return '/' + pathStack.join('/');
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The time complexity of the given code is O(n). This is because we are traversing the entire input path once with the path.split('/') operation, and each of the split operations (inserting into stack and popping from stack) run in constant time O(1). We join the stack at the end to form the simplified path but joining is also linear to the number of elements in the stack, which is at most n.

The space complexity is O(n) as we are potentially storing all the parts of the path in the stack stk. In the worst case scenario, the path does not contain any ".." or "." and is not optimized thus we would have to store each part of the path in the stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫