Generate Parentheses

Q: Độ phức tạp thời gian của Generate Parentheses là bao nhiêu?

Thuật toán quay lui tạo ra C(n) = (2n)! / ((n+1)! n!) chuỗi, tức số Catalan, tăng theo tốc độ 4^n / (n^1.5 √π) . Mỗi chuỗi cần O(n) thời gian để tạo và sao chép, nên độ phức tạp thời gian là O(4^n / √n) . Bộ nhớ phụ là O(n) cho chuỗi hiện tại và ngăn xếp lời gọi, chưa tính kết quả đầu ra.

Q: Có bao nhiêu chuỗi ngoặc đơn hợp lệ với n cặp?

Số Catalan thứ n: 1, 2, 5, 14, 42, 132, 429 và 1,430 khi n chạy từ 1 đến 8. Mỗi chuỗi đúng định dạng đều tách thành ( A ) B, trong đó ) khớp với ( đầu tiên, còn A và B có tổng cộng n - 1 cặp. Cộng theo kích thước của A sẽ cho ta hệ thức truy hồi Catalan.

Q: Có thể giải bài toán tạo dấu ngoặc mà không dùng đệ quy không?

Đúng vậy. Hãy lưu các trạng thái chưa hoàn chỉnh vào một ngăn xếp, mỗi trạng thái là một chuỗi cùng với hai bộ đếm của nó, rồi mở rộng từng trạng thái theo cùng hai quy tắc. Đẩy phần mở rộng ) vào trước phần mở rộng ( , để phần mở rộng ( được lấy ra trước và kết quả vẫn được sắp xếp.

Trung bìnhQuay lui Đệ quy

+10

Một chuỗi dấu ngoặc đơn được xem là hợp lệ nếu khi đọc từ trái sang phải, số lượng ) không bao giờ vượt quá số lượng (, và hai số lượng này bằng nhau ở cuối chuỗi. Vì vậy, (())() hợp lệ, còn ())( thì không: ký tự thứ ba đóng một cặp dấu ngoặc chưa từng được mở.

Cho số nguyên n, hãy trả về mọi chuỗi hợp lệ gồm n dấu ngoặc mở và n dấu ngoặc đóng, được sắp xếp theo thứ tự từ điển, trong đó ( đứng trước ).

Hàm

generateParenthesis(n: integer) → string-array

ninteger: số cặp dấu ngoặc đơn
Trả vềstring-array: mọi chuỗi hợp lệ gồm n cặp, theo thứ tự từ điển

Ràng buộc

1 ≤ n ≤ 8
Với n = 8, đáp án có 1.430 chuỗi.

Ví dụ

Đầu vào: n = 3
Đầu ra: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Giải thích: Có ba cặp tạo thành năm chuỗi đúng định dạng. ((())) mở cả ba cặp trước, nên được xếp đầu tiên; ()()() đóng từng cặp ngay lập tức và được xếp cuối cùng.

Đầu vào: n = 1
Đầu ra: ["()"]
Giải thích: Một cặp có một chuỗi hợp lệ. Cách sắp xếp còn lại duy nhất là )(, đóng trước khi có gì được mở.

Câu hỏi mở rộng

Bạn có thể đếm số chuỗi đúng định dạng cho n cặp mà không cần tạo chúng không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Chỉ một số ít chuỗi có độ dài 2n được tạo thành đúng quy tắc: có 1.430 chuỗi trong tổng số 65.536 chuỗi khi n = 8. Hãy tạo từng chuỗi từ trái sang phải và chỉ thêm một ký tự khi vẫn có thể hoàn thành chuỗi tiền tố. Hai bộ đếm quyết định điều đó, và thử ( trước ) sẽ giúp các chuỗi được sắp xếp.

Tạo từng chuỗi, rồi kiểm tra chúng

Ý tưởng

Điền mọi cách kết hợp ( và ) vào 2n vị trí, tạo ra 4^n chuỗi, rồi giữ lại những chuỗi hợp lệ. Để kiểm tra một chuỗi, hãy duyệt qua chuỗi đó và theo dõi số dư: cộng 1 khi gặp (, trừ 1 khi gặp ). Chuỗi hợp lệ khi số dư không bao giờ nhỏ hơn 0 và kết thúc bằng 0. Ưu tiên đặt ( trước ) tại mỗi vị trí sẽ liệt kê các chuỗi theo thứ tự sắp xếp.

Kiểm tra mỗi chuỗi tốn O(n). Với n = 8, có 65,536 chuỗi nhưng chỉ 1,430 đáp án, nên khoảng 98% công việc bị lãng phí, và số chuỗi tăng gấp bốn lần với mỗi cặp ngoặc bổ sung.

Thuật toán

Giữ một bộ đệm gồm 2n ký tự và một danh sách chứa các câu trả lời.
fill(pos): nếu pos bằng 2n, lưu bộ đệm nếu nó hợp lệ.
Nếu không, đặt ( tại pos rồi gọi fill(pos + 1), sau đó đặt )</code tại đó và gọi lại hàm.</li><li>Để kiểm tra, cộng 1 cho mỗi <code>( và trừ 1 cho mỗi ). Loại bỏ khi số dư nhỏ hơn 0 hoặc không kết thúc ở 0.
Gọi fill(0) và trả về các chuỗi đã lưu.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Quay lui dựa trên số lần mở và đóng

Ý tưởng

Đưa phép kiểm tra vào trong khối lệnh. Một tiền tố có thể phát triển thành chuỗi đúng định dạng khi nó dùng không quá n ký tự ( và không bao giờ có số ký tự ) nhiều hơn số ký tự (. Vì vậy, có thể thêm ( khi opened < n, và thêm ) khi closed < opened. Ở độ dài 2n, cả hai số đếm đều bằng n, và chuỗi đúng định dạng, không còn gì cần kiểm tra.

Không bỏ sót đáp án nào, vì mọi tiền tố của một chuỗi đúng định dạng đều tuân theo cả hai quy tắc. Không có nhánh nào bị lãng phí: với n = 2, nhánh (( chỉ có thể đóng hai lần, tạo thành (()), còn nhánh () chỉ có thể mở rồi đóng, tạo thành ()(). Mỗi chuỗi tương ứng với một đường đi trong cây, nên chỉ xuất hiện một lần; nhánh ( được duyệt trước, vì vậy đầu ra đã được sắp xếp.

Mỗi nút lá là một đáp án, nên lượng công việc tỉ lệ với đầu ra: O(4^n / √n).

Thuật toán

Giữ chuỗi đang được tạo và hai bộ đếm opened và closed, cả hai đều bằng 0.
Nếu chuỗi có độ dài 2n, lưu một bản sao rồi trả về.
Nếu opened < n, thêm (, gọi đệ quy với opened + 1 rồi xóa ký tự đó.
Nếu closed < opened, thêm ), gọi đệ quy với closed + 1 rồi xóa ký tự đó.
Bắt đầu với chuỗi rỗng và trả về các chuỗi đã lưu.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Lỗi thường gặp và trường hợp biên

Cho phép thêm ) khi closed < n thay vì closed < opened. Cách đó tạo ra ())(, trong đó một cặp được đóng dù chưa từng được mở.
Chỉ kiểm tra xem số lượng có khớp ở cuối hay không. Cách đó chấp nhận )(; độ cân bằng phải luôn bằng 0 hoặc lớn hơn ở mọi bước.
Thử ) trước (. Các chuỗi đúng sẽ xuất hiện theo thứ tự ngược lại.
Lưu bộ đệm dùng chung thay vì một bản sao, khi danh sách hoặc trình tạo chuỗi có thể thay đổi. Khi đó, mọi đáp án đã lưu đều hiển thị cùng một bộ đệm, rồi thao tác quay lui lại xóa bộ đệm đó.
Ước lượng số phần tử rồi dùng con số quá nhỏ để tạo mảng kết quả có kích thước cố định. n = 8 có 1.430 đáp án.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Generate Parentheses là bao nhiêu?

Thuật toán quay lui tạo ra C(n) = (2n)! / ((n+1)! n!) chuỗi, tức số Catalan, tăng theo tốc độ 4^n / (n^1.5 √π). Mỗi chuỗi cần O(n) thời gian để tạo và sao chép, nên độ phức tạp thời gian là O(4^n / √n). Bộ nhớ phụ là O(n) cho chuỗi hiện tại và ngăn xếp lời gọi, chưa tính kết quả đầu ra.

Có bao nhiêu chuỗi ngoặc đơn hợp lệ với n cặp?

Số Catalan thứ n: 1, 2, 5, 14, 42, 132, 429 và 1,430 khi n chạy từ 1 đến 8. Mỗi chuỗi đúng định dạng đều tách thành ( A ) B, trong đó ) khớp với ( đầu tiên, còn A và B có tổng cộng n - 1 cặp. Cộng theo kích thước của A sẽ cho ta hệ thức truy hồi Catalan.

Có thể giải bài toán tạo dấu ngoặc mà không dùng đệ quy không?

Đúng vậy. Hãy lưu các trạng thái chưa hoàn chỉnh vào một ngăn xếp, mỗi trạng thái là một chuỗi cùng với hai bộ đếm của nó, rồi mở rộng từng trạng thái theo cùng hai quy tắc. Đẩy phần mở rộng ) vào trước phần mở rộng (, để phần mở rộng ( được lấy ra trước và kết quả vẫn được sắp xếp.

def generateParenthesis(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 3

Đầu ra mong đợi

["((()))", "(()())", "(())()", "()(())", "()()()"]