71. Simplify Path

How to solve Simplify Path (LeetCode 71): the approach in brief

The problem

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

Pattern

Simplify Path is a Stack Patterns problem, in the Simulation / Backtracking Helper subpattern. The pattern covers parentheses matching, monotonic stack, histogram, and expression evaluation

Use stack for simulation problems like simplify path, decode string, and asteroid collision.

Approach outline

1. Consider how you might process the path components sequentially and keep track of directory levels; which data structure naturally supports undoing the last action?
2. Think about splitting the path by slashes to obtain components; how can you handle empty strings or single periods that represent the current directory?
3. When encountering a double period '..', how can you use your data structure to move up one directory level, and how should you handle attempts to go above the root?

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Simplify Path has been reported in interviews at Facebook, Google, Amazon, Microsoft.