Skip to content

06-simplify-path.md

Latest commit

 

History

History
108 lines (80 loc) · 2.72 KB

06-simplify-path.md

File metadata and controls

108 lines (80 loc) · 2.72 KB
Raw
title Simplify Path
difficulty 🟡 Medium
tags
String
Stack
url https://leetcode.com/problems/simplify-path/

Simplify Path

Problem Description

Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this path into its simplified canonical path.

The rules are:

  • A single period '.' represents the current directory
  • A double period '..' represents the parent directory
  • Multiple consecutive slashes '//' are treated as a single slash
  • Any other format of periods (e.g., '...') is treated as a directory name

The canonical path should:

  • Start with a single slash '/'
  • Directories separated by a single slash '/'
  • Not end with a trailing slash (unless it's the root)
  • Not have any . or .. components

Examples

Example 1:

Input: path = "/home/"
Output: "/home"

Example 2:

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

Example 3:

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

Example 4:

Input: path = "/../"
Output: "/"
Explanation: Going up from root stays at root

Constraints

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

Solution

Intuition

A stack naturally handles the parent directory (..) operation: push directories, pop on ... Split the path by /, process each component, and join the final stack.

Algorithm

  1. Split path by '/' and filter out empty strings and '.'
  2. For each remaining component:
    • If '..': pop from stack (if not empty)
    • Otherwise: push directory name onto stack
  3. Join stack with '/' and prepend '/'

Complexity Analysis

  • Time Complexity: $O(n)$ — process each character once
  • Space Complexity: $O(n)$ — stack may hold all directory names
class Solution:
    def simplifyPath(self, path: str) -> str:
        # Split the path by '/' and remove:
        # - empty parts (caused by '//' or leading '/')
        # - '.' since it represents the current directory
        components = [part for part in path.split("/") if part and part != "."]

        stack = []
        for part in components:
            if part == "..":
                # ".." means go up one directory
                # Only pop if there is a directory to go back from
                if stack:
                    stack.pop()
            else:
                # Valid directory name, push onto the stack
                stack.append(part)

        # Rebuild the canonical path from the stack
        # Always starts with a root '/'
        return "/" + "/".join(stack)