064. Simplify an Absolute Unix Path

Foundation · Download this solution · All solutions and shared helpers

Problem

Normalize an absolute Unix-style path lexically. Ignore repeated slashes and '.' components; '..' removes the most recent ordinary component when one exists and stays at root otherwise. Return one leading slash, no trailing slash except at root. Do not inspect a filesystem or resolve symbolic links.

Examples

Example 1

simplify_path("/a/./b/../../c/")
=> '/c'

Two parent components undo b and a.

Example 2

simplify_path("/../../")
=> '/'

Parent navigation cannot move above root.

Example 3

simplify_path("/a//.../b/")
=> '/a/.../b'

Three dots are an ordinary component.

Reveal the worked solution and reasoning

Why this mechanism works

A path component adds a level, while '..' undoes the most recent retained level. A stack represents that reversible history. Dot-like names other than exactly '.' and '..', such as '...', are ordinary names.

State and boundaries

parts is the sequence of retained directory names from root to the current lexical location.

Protocol

Split on slash.
Ignore empty and dot components.
On dot-dot pop a retained component if possible.
Otherwise push the ordinary name.
Join with one slash and prepend root.

Visualization

/a/./b/../../c/
[] -> [a] -> [a,b] -> [a] -> [] -> [c]
result /c

Python implementation

def simplify_path(path):
    parts = []
    for part in path.split('/'):
        if part in ('', '.'):
            continue
        if part == '..':
            if parts:
                parts.pop()
        else:
            parts.append(part)
    return '/' + '/'.join(parts)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

simplify_path("/a/./b/../../c/")

L2 simplify_path: parts = []
path='/a/./b/../../c/'; parts=[]

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=[]; part=''

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=[]; part='a'

L10 simplify_path: parts.append(part)
path='/a/./b/../../c/'; parts=['a']; part='a'

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=['a']; part='.'

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=['a']; part='b'

L10 simplify_path: parts.append(part)
path='/a/./b/../../c/'; parts=['a', 'b']; part='b'

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=['a', 'b']; part='..'

... 1 intermediate state changes omitted ...

L8 simplify_path: parts.pop()
path='/a/./b/../../c/'; parts=[]; part='..'

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=[]; part='c'

L10 simplify_path: parts.append(part)
path='/a/./b/../../c/'; parts=['c']; part='c'

L3 simplify_path: for part in path.split('/'):
path='/a/./b/../../c/'; parts=['c']; part=''

Result: '/c'. Two parent components undo b and a.

simplify_path("/../../")

L2 simplify_path: parts = []
path='/../../'; parts=[]

L3 simplify_path: for part in path.split('/'):
path='/../../'; parts=[]; part=''

L3 simplify_path: for part in path.split('/'):
path='/../../'; parts=[]; part='..'

L3 simplify_path: for part in path.split('/'):
path='/../../'; parts=[]; part=''

Result: '/'. Parent navigation cannot move above root.

Why the solution is correct

Ordinary components extend the path; a parent component removes precisely the latest extension when possible. Ignored components do not change location. These rules preserve lexical path meaning, and joining the retained names gives the canonical form.

Time and space

O(n) time and O(n) space in the path length.

Common mistakes

Treating any name containing dots as special corrupts valid names. Lexical simplification is not symbolic-link resolution.

Reasoning card

State: parts is the sequence of retained directory names from root to the current lexical location.

Invariant: Stack contains normalized path components.

Decision to rehearse: Push normal components; pop on .. when possible.

Finish: Join with one slash and prepend root

Transfer exercise

Specify the different behavior needed for a relative path whose leading '..' components cannot be canceled.