Chương trình tìm số nhảy tối thiểu về thư mục gốc trong Python

Giả sử ta có log đường dẫn vào thư mục với các ký hiệu:

• "../": về thư mục cha (nếu ở gốc thì không đổi)
• "./": ở thư mục hiện tại
• "x/": vào thư mục con tên x

Từ log, tìm số phép toán tối thiểu để quay về thư mục gốc từ thư mục cuối cùng.

Ví dụ: logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"], kết quả 3.

Giải thuật

1. stk := []
2. Với mỗi i trong logs:
   • Nếu i == "../" và len(stk) > 0: stk.pop()
   • Ngược lại nếu i != "./" và i != "../": stk.append(i)
   • Ngược lại: continue
3. Trả về len(stk)

Ví dụ (Python)

def solve(logs):
    stk = []
    for i in logs:
        if i == "../" and len(stk) > 0:
            stk.pop()
        elif i != "./" and i != "../":
            stk.append(i)
        else:
            continue
    return len(stk)

logs = ["Dir1/", "Dir2/", "../", "Dir2/", "Dir3/", "./"]
print(solve(logs))

Input

["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]

Output

3