情境模擬: 資料夾深度 Crawler Log Folder_Leetcode #1598

Garmin B on Unsplash

題目敘述 Crawler Log Folder

題目給定一串目錄進出的操作指令，請問所有指令完成後，回到根目錄需要幾個步驟?

../ 代表回到上一層目錄
./ 代表留在目前的目錄
x/ 代表前往名稱為x的子目錄

測試範例

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 <= 10^3

指令的數量介於1~1000個

• 2 <= logs[i].length <= 10

每個指令的長度介於2~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.

資料夾名稱只會有小寫英文字母和數字

演算法 模擬法

直接根據每一條指令進行模擬

如果遇到../就回到上一層的目錄，深度-1。

如果遇到./就留在目前目錄，深度不改變。

如果遇到x/就進入到下一層名子為x的子目錄，深度+1。

最後，模擬結束時，深度就是回到根目錄所需要的操作次數。

程式碼 模擬法

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        
        level = 0

        for command in logs:

            if command == "../":

                # go backward, up to root(0) at most
                level = max(level-1, 0)
            elif command != "./":

                # go forward
                level += 1

        return level

複雜度分析

時間複雜度: O(n)

線性掃描每個指令，所需時間為O(n)。

空間複查度: O(1)

所用到的都是固定尺寸的臨時變數，為常數級別O(1)。

Reference

[1] Crawler Log Folder - LeetCode