Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Simplify Path
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ".." to the previous directory and removing any "." or multiple slashes. The resulting string should represent the shortest absolute path.

Examples

Example 1

  • Input: path = "/a//b////c/d//././/.."
  • Expected Output: "/a/b/c"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • "." refers to the current directory and is ignored.
    • ".." moves up one directory, so "d" is removed.
    • The simplified path is "/a/b/c".

Example 2

  • Input: path = "/../"
  • Expected Output: "/"
  • Explanation:
    • ".." moves up one directory, but we are already at the root ("/"), so nothing happens.
    • The final simplified path remains "/".

Example 3

  • Input: path = "/home//foo/"
  • Expected Output: "/home/foo"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • The final simplified path is "/home/foo".

Constraints:

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.

Solution

To simplify the path, we'll use a stack to track the directories we're currently in. We'll split the input path into components by the "/" character, then process each component one by one. If a component is "..", we go to the previous directory by popping the top of the stack. If a component is "." or an empty string, we do nothing. Otherwise, we push the component into the stack as a new directory.

Step-by-Step Algorithm

  1. Split the input path by the "/" character into an array of components.

  2. Initialize an empty stack.

  3. For each component in the array:

    • If the component is "..", pop the top of the stack (if it's not already empty).
    • Else if the component is "." or an empty string, do nothing.
    • Else, push the component into the stack as a new directory.

  4. Merge all elements in the stack into a string by reversing the order and joining them with the '/' character. Ensure the final path starts with '/' to represent an absolute path.

Algorithm walkthrough

Image

  1. Initialize a Stack: A Stack<String> is created to store components of the simplified path.

  2. Split the Path: The input path "/a//b////c/d//././/.." is split using "/" as the delimiter. The resulting parts are: ["", "a", "", "b", "", "", "", "c", "d", "", ".", "", ".", "", "", ".."]. Empty strings and dots (".") represent the current directory and will be ignored in further processing.

  3. Process Each Part:

    • First Part (""): It's empty, so it's ignored.
    • Second Part ("a"): It's a directory name and is pushed onto the stack.
    • Third Part (""): Ignored.
    • Fourth Part ("b"): Another directory name, pushed onto the stack.
    • Next Several Parts ("", "", ""): All empty, so ignored.
    • Part "c": A directory name, pushed onto the stack.
    • Part "d": Another directory name, pushed onto the stack.
    • Part ".": Represents the current directory, ignored.
    • Part "." (again): Again, represents the current directory, ignored.
    • Last Part (".."): Represents moving up one directory. It pops "d" from the stack.

    After processing, the stack contains: ["a", "b", "c"].

  4. Reconstruct Simplified Path: Next, create the resulting string by joining all stack elements with the '/' character in reverse order.

    • After processing the stack, the string contains "/a/b/c".

  5. Return the Result:

    • For the given input, the output is "/a/b/c".

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Splitting the path: The input string path is split using / as the delimiter, which takes O(N) time, where N is the length of the input string path. This creates an array of strings representing the components of the path.

  • Processing the components: The algorithm processes each component of the path array. For each component, it either pushes it onto the stack, pops an element from the stack, or skips the component if it is . or empty. Since each component is processed at most once, this takes O(N) time in total.

  • Building the result: After processing all components, the algorithm reconstructs the simplified path by concatenating the elements in the stack. This also takes O(N) time.

Overall time complexity: O(N), where N is the length of the input string path.

Space Complexity

  • Stack space: The stack stores the components of the simplified path. In the worst case, the stack contains all components of the path, which requires O(N) space.

  • Result string space: The result string is used to store the final result which also takes O(N) space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: O(N).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible