Longest Valid Parentheses
Bạn nhận được một chuỗi s chỉ gồm các ký tự ( và ). Hãy tìm chuỗi con dài nhất (một dãy ký tự liên tiếp) có cấu trúc hợp lệ: mỗi ( trong đó đều được đóng bởi một ) xuất hiện sau nó trong chuỗi con, và các cặp được lồng đúng cách, như trong (()()). Trả về độ dài của chuỗi con đó, hoặc 0 nếu không có cả ().
Hàm
- sstring
- một chuỗi gồm các ký tự ( và )
- Trả vềinteger
- độ dài của chuỗi con đúng định dạng dài nhất, hoặc 0 nếu không có
Ràng buộc
1 ≤ s.length ≤ 6 × 104- Mỗi ký tự của
slà(hoặc).
Ví dụ
- Đầu vào
- s = "()(())"
- Đầu ra
- 6
- Giải thích
- Toàn bộ chuỗi đều hợp lệ:
()theo sau là(()). Ghép hai phần hợp lệ cạnh nhau sẽ tạo thành một phần, vậy nên đáp án gồm đủ 6 ký tự.
- Đầu vào
- s = "())((())"
- Đầu ra
- 4
- Giải thích
)ở chỉ số 2 không có dấu ngoặc tương ứng, nên không có lời giải nào vượt qua nó, còn(ở chỉ số 3 không bao giờ được đóng. Đoạn dài nhất là(())ở các chỉ số từ 4 đến 7, có độ dài 4, dài hơn()ở đầu.
- Đầu vào
- s = "))(("
- Đầu ra
- 0
- Giải thích
- Cả hai
)đều đứng trước cả hai(, nên không có(nào được đóng và đáp án là 0.
Câu hỏi mở rộng
Bạn cũng có thể cho biết vị trí bắt đầu của chuỗi con hợp lệ dài nhất, chọn chuỗi nằm bên trái nhất nếu có nhiều chuỗi cùng độ dài không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Đọc một chuỗi con từ trái sang phải và duy trì số dư: +1 cho
(, -1 cho). Số dư sẽ thay đổi thế nào trong một chuỗi con đúng định dạng, và một)khiến số dư giảm xuống dưới 0 cho bạn biết điều gì về mọi chuỗi con đi qua nó?Giữ một ngăn xếp chứa các chỉ số của những ký tự
(chưa được đóng. Khi)đóng ký tự ở trên cùng, đoạn hợp lệ kết thúc tại đây bắt đầu ngay sau chỉ số hiện còn ở trên cùng. Khi không có gì đang mở, bạn nên đặt gì vào ngăn xếp?Bắt đầu ngăn xếp với -1, chỉ số ngay trước chuỗi. Đẩy chỉ số của mọi
(vào ngăn xếp. Khi gặp), hãy lấy một chỉ số ra; nếu ngăn xếp lúc này trống, không thể ghép cặp)này, vì vậy hãy đẩy chỉ số của nó vào làm mốc mới; nếu không, độ dài đoạn hiện tại làitrừ đi chỉ số ở đầu ngăn xếp. Giữ lại đoạn dài nhất bạn đo được.
Lời giải
Các phần có cấu trúc hợp lệ sẽ nối liền khi chạm nhau, vì vậy () và (()) đặt cạnh nhau tạo thành một đoạn liên tiếp. Một ký tự lạc chỗ, như ) trong ())(()), sẽ ngắt chuỗi nên không đoạn liên tiếp nào vượt qua nó. Trong một lượt duyệt, một ngăn xếp các chỉ số cùng một dấu mốc cơ sở theo dõi vị trí bắt đầu của đoạn hiện tại; hai lượt duyệt dùng bộ đếm cũng làm được việc đó với bộ nhớ O(1).
Mở rộng chuỗi con từ mỗi vị trí bắt đầu
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Chọn một vị trí bắt đầu và đi sang phải, đồng thời theo dõi số dư: +1 cho (, -1 cho ). Đoạn con đúng định dạng khi và chỉ khi số dư trở về 0 mà không xuống dưới 0, vì vậy hãy ghi lại độ dài mỗi khi số dư chạm 0. Nếu số dư xuống dưới 0, hãy dừng lại: dấu ) đó vẫn không ghép cặp trong mọi đoạn con dài hơn bắt đầu từ vị trí này.
Với 59998 dấu ( theo sau là (), mỗi vị trí bắt đầu đều đi đến cuối: khoảng n²/2 = 1.8 × 10^9 bước với n = 6 × 10^4.
Thuật toán
- Đặt
bestbằng 0. - Với mỗi vị trí bắt đầu, đặt
balancebằng 0 rồi duyệt vị trí kết thúc từ vị trí bắt đầu đến ký tự cuối cùng. - Cộng 1 cho
(và trừ 1 cho). - Nếu
balancenhỏ hơn 0, hãy dừng tại vị trí bắt đầu này. Nếu bằng 0, cập nhậtbestbằngend - start + 1. - Trả về
best.
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return bestNgăn xếp chỉ số có dấu mốc cơ sở
Ý tưởng
Đẩy các chỉ số vào ngăn xếp và giữ thêm một chỉ số ở đáy: mốc gốc, vị trí ngay trước đoạn hiện tại, là -1 lúc bắt đầu. Khi gặp (, đẩy chỉ số của nó vào ngăn xếp. Khi gặp ), lấy một chỉ số ra khỏi ngăn xếp. Nếu ngăn xếp lúc này rỗng, bạn đã lấy mốc gốc ra: ) này không thể đóng cặp nào, nên chỉ số của nó trở thành mốc gốc mới. Nếu không, phần tử trên cùng là ký tự cuối cùng trước đoạn kết thúc tại i, một dấu ( chưa đóng hoặc mốc gốc, nên độ dài đoạn là i - top.
Mốc gốc giúp nối các đoạn liền nhau. Với ()(()), dấu ) cuối cùng lấy chỉ số 2 ra và thấy -1 ở trên cùng: 5 - (-1) = 6. Với ())((()), chỉ số 2 lấy mốc gốc ra và trở thành mốc gốc mới, còn dấu ) cuối cùng lấy chỉ số 4 ra và thấy dấu ( chưa đóng ở vị trí 3: 7 - 3 = 4.
Mỗi chỉ số được đẩy vào và lấy ra khỏi ngăn xếp nhiều nhất một lần: thời gian O(n).
Thuật toán
- Bắt đầu với một ngăn xếp chứa -1 và đặt
bestthành 0. - Với mỗi chỉ số
i, đẩyivào ngăn xếp nếus[i]là(. - Nếu là
), lấy một phần tử ra khỏi ngăn xếp. - Nếu ngăn xếp hiện trống, đẩy
ivào làm mốc mới. Nếu không, cập nhậtbestbằngi - top. - Trả về
best.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestĐếm lượt mở và đóng trong hai lượt
Ý tưởng
Đi từ trái sang phải, đếm opens và closes kể từ lần đặt lại gần nhất. Số lượng bằng nhau nghĩa là mọi thứ kể từ lần đặt lại đều đúng cấu trúc, có độ dài 2 × closes. Khi closes nhiều hơn, một ) không có ký tự ghép cặp, nên đặt lại cả hai. Một ( không bao giờ được đóng sẽ khiến opens luôn nhiều hơn, vì vậy lượt duyệt này không tìm thấy gì trong ((). Đi lại từ phải sang trái, đặt lại khi opens nhiều hơn và giữ lại đáp án lớn hơn.
Hai lượt duyệt là đủ. Đoạn dài nhất được ngăn cách bởi các ký tự không thể ghép cặp hoặc bởi hai đầu chuỗi. Nếu ranh giới bên trái là một ) thừa hoặc là đầu chuỗi, lượt duyệt từ trái sang phải sẽ đặt lại tại điểm bắt đầu đoạn. Nếu ranh giới bên trái là một ( thừa, ranh giới bên phải không thể là ), vì ký tự đó sẽ đóng ( và kéo dài đoạn, nên lượt duyệt từ phải sang trái sẽ tìm thấy đoạn ấy.
Thuật toán
- Đặt
best,opensvàclosesthành 0. - Duyệt từ trái sang phải, đếm từng ký tự. Khi hai bộ đếm bằng nhau, cập nhật
bestbằng2 × closes. Khicloseslớn hơn, đặt lại cả hai về 0. - Đặt lại cả hai bộ đếm, rồi duyệt từ phải sang trái theo cách tương tự, đặt lại khi
openslớn hơn. - Trả về
best.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
Lỗi thường gặp và trường hợp biên
- Đếm các cặp khớp nhau trong toàn bộ chuỗi.
())((())có 3 cặp, nhưng chúng không liền kề nhau, nên đáp án là 4, không phải 6. - Đo đoạn liên tiếp bắt đầu từ dấu
(khớp với dấu đóng. Trong()(()), dấu)cuối cùng khớp với chỉ số 2, cho kết quả 4 và bỏ sót()ở phía trước. - Bắt đầu bằng một ngăn xếp rỗng thay vì giá trị gốc -1 (0 trong Lua và R, vì vị trí bắt đầu từ 1). Khi đó, dấu
)đầu tiên trong())không có gì để đối chiếu. - Chỉ chạy các bộ đếm theo một hướng.
(()trả về 0 khi duyệt từ trái sang phải, còn())trả về 0 khi duyệt từ phải sang trái; đáp án của cả hai đều là 2. - Đặt lại các bộ đếm khi chúng bằng nhau. Đoạn liên tiếp vẫn có thể dài thêm, như trong
()().
Câu hỏi thường gặp3
Độ phức tạp thời gian của bài toán dấu ngoặc hợp lệ dài nhất là gì?
Lời giải dùng ngăn xếp và lời giải dùng bộ đếm qua hai lượt đều chạy trong thời gian O(n). Trong trường hợp xấu nhất, chẳng hạn với chuỗi chỉ gồm (, ngăn xếp cần O(n) bộ nhớ, còn các bộ đếm chỉ cần O(1). Thử mọi vị trí bắt đầu có độ phức tạp O(n²).
Có lời giải quy hoạch động cho bài toán dấu ngoặc hợp lệ dài nhất không?
Có. Gọi end[i] là đoạn ngoặc hợp lệ dài nhất kết thúc tại i, bằng 0 khi s[i] là (. Nếu s[i-1] là (, end[i] = end[i-2] + 2. Nếu không, đặt j = i - end[i-1] - 1; nếu s[j] là (, end[i] = end[i-1] + 2 + end[j-1]. Giá trị end[i] lớn nhất chính là đáp án.
Điều này khác gì so với dấu ngoặc hợp lệ?
Bài toán Dấu ngoặc hợp lệ yêu cầu xác định toàn bộ chuỗi có đúng định dạng hay không, một câu trả lời có hoặc không mà một biến đếm hoặc ngăn xếp có thể đưa ra. Ở đây, bạn cần tìm chuỗi con đúng định dạng dài nhất, vì vậy bạn cũng theo dõi vị trí bắt đầu của mỗi đoạn và bắt đầu lại sau một ký tự không thể ghép cặp.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def longestValidParentheses(s):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
s = "()(())"
Đầu ra mong đợi
6