{x}
blog image

Crawler Log Folder

The Leetcode file system keeps a log each time some user performs a change folder operation.

The operations are described below:

  • "../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
  • "./" : Remain in the same folder.
  • "x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

 

Example 1:

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Example 2:

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

 

Constraints:

  • 1 <= logs.length <= 103
  • 2 <= logs[i].length <= 10
  • logs[i] contains lowercase English letters, digits, '.', and '/'.
  • logs[i] follows the format described in the statement.
  • Folder names consist of lowercase English letters and digits.

Solution Explanation for Crawler Log Folder

This problem involves simulating a file system's folder navigation based on a sequence of operations. The goal is to determine the minimum number of operations needed to return to the root folder after performing all given operations.

Approach:

The most efficient way to solve this problem is using a single integer variable to track the current depth in the file system. We iterate through the logs array. For each log entry:

  • ../: This moves us up one level. If we're already at the root (depth 0), we stay at depth 0. We use max(0, ans - 1) to ensure the depth never goes below 0.

  • ./: This keeps us in the same folder, so we do nothing.

  • x/ (where x is a folder name): This moves us down one level, so we increment our depth counter.

Finally, the value of the depth counter represents the minimum number of ../ operations needed to return to the root folder.

Time and Space Complexity Analysis:

  • Time Complexity: O(N), where N is the length of the logs array. We iterate through the array once.

  • Space Complexity: O(1). We use only a constant amount of extra space to store the depth variable.

Code Implementation (Python):

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        ans = 0  # Initialize the current depth
        for v in logs:
            if v == "../":
                ans = max(0, ans - 1) # Move up, stay at 0 if already at root
            elif v[0] != ".": #Check if it's not "./"
                ans += 1       # Move down
        return ans

Code Implementation in other languages:

The logic remains consistent across languages. The key difference lies in syntax and handling of string comparisons. See the multi-language code example provided in the original response for implementations in Java, C++, Go, TypeScript, Javascript, Rust, and C. They all follow the same depth-tracking approach outlined above.

Example Walkthrough (Python):

Let's trace the execution for logs = ["d1/", "d2/", "../", "d21/", "./"]:

  1. d1/: ans becomes 1.
  2. d2/: ans becomes 2.
  3. ../: ans becomes 1.
  4. d21/: ans becomes 2.
  5. ./: ans remains 2.

The function returns 2, indicating that two ../ operations are needed to return to the root.