Solving the LeetCode "Simplify Path" Problem in Go

Difficulty: Medium | Tags: String, Stack

Introduction

Simplifying file paths is a common task in Unix-like systems. The problem requires converting an absolute path into its canonical form by resolving redundant slashes, single dots (.), and double dots (..). This ensures the path is clean and unambiguous.

Problem Analysis

The input is an absolute path string, and the output must be its simplified version. Key rules include collapsing multiple slashes into one, resolving "." (current directory) and ".." (parent directory), and ensuring the path starts and ends correctly. For example, "/home//foo/" simplifies to "/home/foo", and "/../" simplifies to "/".

Solution Approach

We use a stack to process the path components. Splitting the path by slashes allows us to handle each segment individually. For each segment, we ignore empty strings and ".", pop the stack for "..", and push valid directory names otherwise. The stack helps efficiently manage the directory hierarchy.

Go Implementation

package main
import (
"strings"
)
func simplifyPath(path string) string {
    stack := []string{}
    components := strings.Split(path, "/")
    for _, component := range components {
        if component == "" || component == "." {
            continue
        }
        if component == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else {
            stack = append(stack, component)
        }
    }
    return "/" + strings.Join(stack, "/")
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the path. Splitting the string and processing each component takes linear time.
Space Complexity: O(n), due to the stack storing path components.

Testing and Examples

Test cases include:
1. Input: "/home/" → Output: "/home"
2. Input: "/home//foo/" → Output: "/home/foo"
3. Input: "/../" → Output: "/"
4. Input: "/.../a/../b/c/../d/./" → Output: "/.../b/d"
Edge cases involve paths with multiple slashes, leading/trailing slashes, and sequences of dots.

Best Practices and Tips

1. Use a stack to efficiently handle directory navigation.
2. Split the path by slashes to isolate components.
3. Handle edge cases like empty paths or root directory explicitly.
4. Avoid string concatenation in loops for better performance.