71. Simplify Path

Problem

Bạn cần xử lý một chuỗi đường dẫn tuyệt đối kiểu Unix và trả về đường dẫn đã được rút gọn theo quy tắc sau:

Loại bỏ các dấu slash dư thừa (nhiều dấu // liền nhau chỉ tính là một /)

Bỏ qua ‘.’ (thư mục hiện tại)

Khi gặp ‘..’ quay lại thư mục cha (nếu có)

Kết quả phải bắt đầu bằng ‘/’ và không có slash cuối cùng (trừ trường hợp chỉ là ‘/’)

Approach

Tách đường dẫn thành các phần bằng dấu ‘/’

Duyệt từng phần

Nếu là rỗng hoặc ‘.’ bỏ qua

Nếu là ‘..’ loại bỏ phần tử cuối cùng trong stack (nếu có)

Nếu là thư mục hợp lệ, thêm vào stack

Kết quả là nối các phần trong stack lại với nhau bằng ‘/’ và thêm dấu ‘/’ ở đầu

Time and space complexity

TC: O(n) với n là độ dài của chuỗi’

SC: O(n), trong trường hợp xấu nhất phải lưu tất cả các phần vào stack

Solution

typescripttypescript

1function simplifyPath(path: string): string {
2    const stack: string[] = [];
3    for (const segment of path.split('/')) {
4        if (segment === '' || segment === '.') continue;
5        if (segment === '..') {
6            if (stack.length) stack.pop()
7        } else {
8            stack.push(segment)
9        }
10    }
11
12    return '/' + stack.join('/')
13};

Loading content...