Simplify Path medium

Problem Statement

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-like file system, convert it to the simplified canonical path.

In a Unix-like file system, a period . refers to the current directory, a double period .. refers to the parent directory, and multiple slashes / are treated as a single slash. For instance, the path /home//foo//bar/./baz can be simplified to /home/foo/bar/baz.

Constraints:

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, ., / and ...

Example 1

  • Input: path = "/home/"
  • Output: "/home"
  • Explanation: Note that there is no trailing slash after the last directory name.

Example 2

  • Input: path = "/../"
  • Output: "/"
  • Explanation: Going one level up from the root directory is still in the root directory.

Example 3

  • Input: path = "/home//foo/"
  • Output: "/home/foo"
  • Explanation: Multiple consecutive slashes are treated as a single slash.

Steps

  1. Split the path: Split the input path string into parts using the / character as a delimiter. Ignore empty parts resulting from consecutive slashes.

  2. Process each part: Iterate through the parts.

    • If the part is ".", ignore it (it represents the current directory).
    • If the part is ".." and the stack is not empty, pop the last element from the stack (representing going up one directory).
    • If the part is neither "." nor ".." (a directory name), push it onto the stack.

  3. Construct the simplified path: Join the elements in the stack with / as a separator. Add a leading / if the stack is not empty.

Explanation

The solution uses a stack data structure to efficiently handle the directory traversal. The stack keeps track of the current directory path as we process each part of the input. When we encounter "..", we simply pop from the stack, representing moving up a directory level. "." is ignored because it represents the current directory, leaving the path unaffected. Regular directory names are pushed onto the stack, building up the simplified path.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string SimplifyPath(string path) {
        var parts = path.Split('/').Where(p => !string.IsNullOrEmpty(p)).ToArray();
        var stack = new Stack<string>();

        foreach (var part in parts) {
            if (part == ".") continue;
            if (part == "..") {
                if (stack.Count > 0) stack.Pop();
            } else {
                stack.Push(part);
            }
        }

        var simplifiedPath = string.Join("/", stack.Reverse().ToArray());
        return string.IsNullOrEmpty(simplifiedPath) ? "/" : "/" + simplifiedPath;
    }
}

Complexity

  • Time Complexity: O(N), where N is the length of the input string. We iterate through the parts of the path once.
  • Space Complexity: O(N) in the worst case, where N is the length of the input string. The stack could potentially store all parts of the path if there are no ".." to remove elements. In the best case, space complexity is O(1).