71. Simplify Path

Simplify Path (LeetCode 71) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Simulation / Backtracking Helper subpattern.

• NeetCode 250 · #56 of 250 · Stack

How to solve Simplify Path

Simplify Path is a Stack for Simulation and Backtracking problem, part of Stack Patterns. Use stack for simulation problems like simplify path, decode string, and asteroid collision.

Work towards the solution in these steps:

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?

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

The Simplify Path solution and editorial walks through the full approach with reference code.

Problem statement

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.

The rules of a Unix-style file system are as follows:

- A single period '.' represents the current directory.

- A double period '..' represents the previous/parent directory.

- Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.

- Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

- The path must start with a single slash '/'.

- Directories within the path must be separated by exactly one slash '/'.

- The path must not end with a slash '/', unless it is the root directory.

- The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

Example 1:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

Example 2:

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

Output: "/home/foo"

Explanation:

Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = "/home/user/Documents/../Pictures"

Topics and companies

Topics: String, Stack.

Reported in interviews at Facebook, Google, Amazon, Microsoft.

How to practise Simplify Path on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Simplify Path in the code editor, or read the Simplify Path editorial for a worked solution with its approach and complexity analysis.

Where Simplify Path sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Simulation / Backtracking Helper subpattern
• The full DSA patterns sheet

Problems related to Simplify Path

Other problems that use the same Simulation / Backtracking Helper and Stack Patterns techniques:

• Asteroid Collision — Medium, same subpattern
• Baseball Game — Easy, same subpattern
• Decode String — Medium, same subpattern
• Reconstruct Itinerary — Hard, same subpattern
• Basic Calculator — Hard, same pattern
• Basic Calculator II — Medium, same pattern

Simplify Path FAQ