MediumStringStack

Simplify Path

1 approach, code in every language

You are given a string that represents an absolute path in a Unix-style file system, always beginning with a single slash. The path may contain redundant elements: a single period refers to the current directory, a double period refers to the parent directory, and repeated slashes act as a single separator.

Transform the path into its canonical form. The canonical path starts with exactly one slash, joins directory names with a single slash between them, never ends with a trailing slash unless it is the root, and contains no period or double-period components.

Return the simplified canonical path as a string.

Example 1

Input: path = "/home//foo/"

Output: "/home/foo"

Multiple slashes collapse into one and the trailing slash is removed, leaving two real directories.

Example 2

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

Output: "/c"

The '.' is ignored, and each '..' cancels the most recent directory, so a and b are removed before c is appended.

Constraints

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

Split and Stack

Split the path on slashes and use a stack, pushing real names, popping on '..', and ignoring '.' and empty tokens.

Loading animation…

Intuition

Splitting the path on the slash character breaks it into tokens where each token is either a directory name, a single period, a double period, or an empty string produced by consecutive slashes. A stack mirrors how a file system tracks the current directory chain: entering a named directory pushes it, and moving up with a double period pops the most recent one. The current-directory token and empty tokens carry no information, so we simply skip them. When popping on a double period we must guard against an empty stack, since going above the root just stays at the root. Rebuilding the answer is then a matter of prefixing each remaining stack entry with a slash.

Algorithm walkthrough

1Split the input string on the slash character to obtain a list of raw tokens.
2Iterate over the tokens, skipping any that are empty or equal to a single period.
3When the token is a double period, pop the stack if it is non-empty so you move up one directory.
4Otherwise treat the token as a real directory name and push it onto the stack.
5After processing every token, join the stack entries with a slash separator.
6Prefix the joined result with a leading slash so the root is always present, which also yields '/' when the stack is empty.

Implementation

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for token in path.split('/'):
            if token == '' or token == '.':
                continue
            if token == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(token)
        return '/' + '/'.join(stack)

Time

O(n)

Space

O(n)

The split scans the string once, and each token is pushed or popped at most once. The stack and output are bounded by the input length.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Canonical Store Locator is our own problem on the technique behind Simplify Path: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free